Loại bỏ tất cả các bản sao liền kề trong chuỗi II trong C ++

Giả sử một chuỗi s được đưa ra, việc loại bỏ k trùng lặp bao gồm việc chọn k chữ cái liền kề và bằng nhau từ chuỗi s và loại bỏ chúng khiến bên trái và bên phải của chuỗi con bị xóa ghép lại với nhau. Chúng tôi sẽ lặp đi lặp lại k lần xóa trùng lặp trên chuỗi s đã cho cho đến khi chúng tôi không thể thay đổi bất kỳ chuỗi nào còn lại. Chúng tôi phải tìm chuỗi cuối cùng sau khi tất cả các lần xóa trùng lặp như vậy đã được thực hiện. Vì vậy, nếu đầu vào là s =​​“deeedbbcccbdaa” và k =3, thì đầu ra sẽ là “aa”, lúc đầu hãy xóa “eee” và “ccc” và chúng ta sẽ nhận được “ddbbbaa”, sau đó xóa “bbb” , chuỗi sẽ là “dddaa”, sau đó xóa “ddd” và đầu ra sẽ là “aa”

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ans:=chuỗi trống
• tạo một ngăn xếp cho cặp char-int, n:=kích thước của chuỗi
• cho tôi trong phạm vi từ 0 đến n
  • x:=s [i]
  • nếu ngăn xếp không trống và là số nguyên của phần tử trên cùng ngăn xếp =k, thì hãy xóa phần tử trên cùng khỏi ngăn xếp
  • nếu i =n, thì ngắt
  • nếu ngăn xếp trống hoặc ký tự của đỉnh ngăn xếp không phải là x, thì hãy chèn cặp (x, 1) vào ngăn xếp và tăng i lên 1
  • nếu không, hãy tăng phần nguyên của phần tử trên cùng của ngăn xếp và tăng i lên 1
• trong khi ngăn xếp không trống
  • temp:=phần tử trên cùng của ngăn xếp
  • trong khi phần nguyên của tạm thời không phải là 0,
    • ans:=ans + một phần ký tự của tạm thời
    • giảm phần nguyên của nhiệt độ xuống 1
  • xóa phần tử trên cùng khỏi ngăn xếp
• đảo ngược chuỗi ans và trả về.

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

"deeedbbcccbdaa"
3

Đầu ra

aa