C++の文字列IIで隣接するすべての重複を削除します

文字列sが与えられたとすると、k重複削除は、文字列sからk個の隣接する等しい文字を選択し、それらを削除して、削除されたサブ文字列の左側と右側を連結することで構成されます。残りを変更できなくなるまで、指定された文字列に対してk回の重複削除を繰り返し行います。このような重複した削除がすべて行われた後、最終的な文字列を見つける必要があります。したがって、入力がs =“ deeedbbcccbdaa”のようで、k =3の場合、出力は“ aa”になります。最初に“ eee”と“ ccc”を削除すると、“ ddbbbaa”が取得され、次に“ bbb”が削除されます。 、文字列は「dddaa」になり、次に「ddd」を削除すると、出力は「aa」になります

これを解決するには、次の手順に従います-

• ans：=空の文字列
• char-intペア用に1つのスタックを作成し、n：=文字列のサイズ
• 0からnの範囲のiの場合
  • x：=s [i]
  • スタックが空でなく、スタックの最上位要素の整数=kの場合、スタックから最上位の要素を削除します
  • i =nの場合、中断します
  • スタックが空であるか、スタックトップの文字がxでない場合は、ペア（x、1）をスタックに挿入し、iを1増やします
  • それ以外の場合は、スタックトップ要素の整数部分を増やし、iを1増やします
• スタックが空でない間
  • temp：=スタックトップ要素
  • tempの整数部分が0でない場合、
    • ans：=ans+tempの文字部分
    • tempの整数部分を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