สมมติว่าสตริง s ได้รับ การลบซ้ำ k ประกอบด้วยการเลือก k ตัวอักษรที่อยู่ติดกันและเท่ากับจากสตริง s และการลบออกทำให้ด้านซ้ายและด้านขวาของสตริงย่อยที่ถูกลบเชื่อมต่อเข้าด้วยกัน เราจะทำการลบซ้ำ k ครั้งในสตริงที่กำหนด s จนกว่าเราจะไม่สามารถเปลี่ยนแปลงส่วนที่เหลือได้ เราต้องหาสตริงสุดท้ายหลังจากลบที่ซ้ำกันทั้งหมดแล้ว ดังนั้นหากอินพุตเป็น s =“deeedbbcccbdaa” และ k =3 ผลลัพธ์จะเป็น “aa” ในตอนแรกให้ลบ “eee” และ “ccc” แล้วเราจะได้ “ddbbbaa” จากนั้นให้ลบ “bbb” สตริงจะเป็น "dddaa" จากนั้นลบ "ddd" และผลลัพธ์จะเป็น "aa"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ตอบ :=สตริงว่าง
- สร้างหนึ่งสแต็กสำหรับคู่อักขระ n :=ขนาดของสตริง
- สำหรับฉันอยู่ในช่วง 0 ถึง n
- x :=s[i]
- ถ้า stack ไม่ว่างและเป็นจำนวนเต็มของ stack top element =k ให้ลบองค์ประกอบด้านบนออกจาก stack
- ถ้า i =n ก็แตก
- ถ้า stack ว่างเปล่าหรือตัวอักษรของ stack top ไม่ใช่ x ให้ใส่คู่ (x, 1) เข้าไปใน stack และเพิ่ม i ขึ้น 1
- มิฉะนั้น ให้เพิ่มส่วนจำนวนเต็มขององค์ประกอบบนสุดของสแต็ก และเพิ่ม i ขึ้น 1
- ในขณะที่สแต็กไม่ว่างเปล่า
- temp :=stack องค์ประกอบบนสุด
- ในขณะที่ส่วนจำนวนเต็มของ temp ไม่ใช่ 0,
- ans :=ans + ส่วนอักขระของอุณหภูมิ
- ลดส่วนจำนวนเต็มของอุณหภูมิลง 1
- ลบองค์ประกอบด้านบนออกจากสแต็ก
- ย้อนกลับสตริง ans และย้อนกลับ
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string removeDuplicates(string s, int k) {
string ans = "";
stack < pair<char, int> > st;
int n = s.size();
for(int i = 0; i <= n;){
char x = s[i];
if(!st.empty() && st.top().second == k)st.pop();
if(i == n)break;
if(st.empty() || st.top().first != x){
st.push({x, 1});
i++;
} else {
st.top().second++;
i++;
}
}
while(!st.empty()){
pair <char, int> temp = st.top();
while(temp.second--) ans += temp.first;
st.pop();
}
reverse(ans.begin(), ans.end());
return ans;
}
};
main(){
Solution ob;
cout <<(ob.removeDuplicates("deeedbbcccbdaa", 3));
} อินพุต
"deeedbbcccbdaa" 3
ผลลัพธ์
aa
