Pythonで文字列内の隣接する重複文字をすべて削除する方法

問題の概要

小文字のみで構成された文字列 S が与えられたとします。この文字列に対して「重複削除操作」を行います。これは、隣り合っていて等しい2つの文字を選び、それらを削除するというものです。

この操作を繰り返し適用し、文字列 S に隣接する重複がなくなるまで削除を続けます。そして、すべての重複削除が完了した後の文字列を返します。なお、答えは一意であることが保証されています。

具体例

例えば、文字列が「abbacaca」の場合、答えは「caca」となります。処理の流れを見てみましょう。

• まず「bb」を削除すると、文字列は「aacaca」になります
• 次に先頭の「aa」を削除すると、文字列は「caca」になります
• これ以上削除できる隣接する重複は存在しないため、「caca」が最終的な答えとなります

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

この問題はスタック（stack）を使うことで効率的に解くことができます。手順は以下の通りです。

1. 空の配列 st を定義し、インデックス i を 0 で初期化します
2. i が文字列の長さ未満である間、以下を繰り返します
   • st に要素があり、かつ st の末尾の要素が S[i] と等しい場合：i を1増やし、st の末尾の要素を削除（pop）します
   • そうでない場合：S[i] を st の末尾に追加（append）し、i を1増やします
3. 最後に、st 内のすべての要素を連結して文字列として返します

このアルゴリズムの計算量は O(n) です。各文字は最大1回プッシュされ、最大1回ポップされるだけなので、非常に効率的に動作します。

実装例

以下のコードで実際の実装を確認してみましょう。

class Solution(object):
    def removeDuplicates(self, S):
        st = []
        i = 0
        while i < len(S):
            if len(st) != 0 and st[-1] == S[i]:
                i += 1
                st.pop(-1)
            else:
                st.append(S[i])
                i += 1
        return "".join(i for i in st)

ob1 = Solution()
print(ob1.removeDuplicates("abbacaca"))

入力

"abbacaca"

出力

"caca"

まとめ

隣接する重複文字の削除問題は、スタックの「後入れ先出し（LIFO）」という性質を利用することで、直感的かつ効率的に解決できます。文字を順番に読み込みながら、スタックの末尾と比較して一致すれば削除、一致しなければ追加というシンプルな処理の繰り返しがポイントです。同様のパターンは、括弧の対応チェックや文字列の圧縮など、さまざまな文字列処理の問題にも応用できるので、ぜひ覚えておきましょう。