在C ++中删除字符串II中的所有相邻重复项

假设给出了字符串s，则ak重复删除包括从字符串s中选择k个相邻且相等的字母，然后删除它们，使删除的子字符串的左侧和右侧连接在一起。我们将在给定的字符串s上重复进行k次重复删除，直到无法更改任何剩余项为止。完成所有此类重复删除后，我们必须找到最终字符串。因此，如果输入类似于s =“ deeedbbcccbdaa”，且k = 3，则输出将为“ aa”，首先删除“ eee”和“ ccc”，我们将得到“ ddbbbaa”，然后删除“ bbb” ，字符串将是“ dddaa”，然后删除“ ddd”，输出将是“ aa”

为了解决这个问题，我们将遵循以下步骤-

• ans：=空字符串

• 为char-int对创建一个堆栈，n：=字符串的大小

• 当我的范围是0到n

• x：= s [i]

• 如果堆栈不为空并且堆栈顶部元素的整数= k，则从堆栈中删除顶部元素

• 如果i = n，则破坏

• 如果堆栈为空或堆栈顶部的字符不是x，则将对(x,1)插入堆栈，并将i加1

• 否则增加栈顶元素的整数部分，并将i增加1

• 当堆栈不为空时

• ans：= ans + temp的字符部分

• 将温度的整数部分减少1

• temp：=堆栈顶部元素

• 虽然temp的整数部分不为0，

• 从堆栈中删除顶部元素

• 反转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