【C++】文字列から隣接するk個の重複をすべて削除するアルゴリズム

文字列 s と整数 k が与えられた状況を考えてみましょう。「k個の重複削除」とは、文字列の中から隣接する k 個の同一文字を選んで取り除き、削除した部分の左側と右側をつなぎ合わせる操作のことです。この操作を、それ以上文字列を変更できなくなるまで繰り返し適用し、最終的に残る文字列を求めるのが本問題の目的です。

具体例で確認しよう

入力が s = "deeedbbcccbdaa"、k = 3 の場合を順に追ってみます。

• まず "eee" を削除 → "ddbbcccbdaa"
• 次に "ccc" を削除 → "ddbbbdaa"
• さらに "bbb" を削除 → "dddaa"
• 最後に "ddd" を削除 → "aa"

したがって、この場合の出力は "aa" となります。

解法のアプローチ：スタックを活用する

この問題は「スタック」を使うことで効率的に解けます。各スタック要素には「文字」と「その文字が連続して現れた回数」のペアを格納するのがポイントです。手順は以下の通りです。

• 答えを格納する文字列 ans を空文字列で初期化する。
• (char, int) ペアを保持できるスタックを作成し、n := 文字列の長さとする。
• i が 0 から n までの間、以下を繰り返す。
  • x := s[i] とする。
  • スタックが空でなく、スタックトップのカウントが k に等しければ、トップ要素を取り除く（pop）。
  • i == n ならばループを抜ける。
  • スタックが空、またはスタックトップの文字が x と異なる場合は、ペア (x, 1) をプッシュし、i を 1 増やす。
  • そうでなければ、スタックトップのカウントを 1 増やし、i を 1 増やす。
• スタックが空になるまで、以下を繰り返す。
  • temp := スタックトップ要素とする。
  • temp のカウントが 0 になるまで、ans に temp の文字を追加し、カウントを 1 減らす。
  • スタックトップを取り除く。
• 最後に ans を反転させて返す。

それでは、実際の実装を見て理解を深めましょう。

C++実装例

#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

計算量の評価

時間計算量： O(n)。各文字はスタックへの登録時に1回、結果文字列の構築時に最大1回処理されるため、全体で文字列長に対して線形時間で完了します。

空間計算量： O(n)。最悪ケースでは、すべての文字が異なる場合にスタックへ n 個の要素が格納され得ます。

このようにスタックで「文字と連続回数」を管理することで、削除後の連結による新たな重複も自動的に検出でき、繰り返し削除が必要なケースにも一括して対応できます。