Pythonで連続する重複文字を削除した後に残る文字列を求めるプログラム

問題の概要

文字列 s が与えられます。先頭側から見て最初に現れる「連続した重複文字」を繰り返し削除していき、最終的に残る文字列を求めます。

たとえば、入力が s = "xyyyxxz" の場合を考えてみましょう。まず "yyy" という連続する重複文字が削除されて "xxxz" となり、続いて "xxx" が削除されるため、最終的な出力は "z" になります。

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

この問題は、スタック（後入れ先出し・LIFO）というデータ構造を使うと効率的に解けます。アルゴリズムの手順は以下のとおりです。

• 空のスタックを用意し、インデックス i を 0 で初期化する。
• i が文字列の長さ未満である間、以下を繰り返す。
  • スタックが空でなく、スタックのトップが現在の文字 s[i] と一致する場合：トップの要素を取り出して x とし、x と同じ文字が続く限り i を進める。その後、i を 1 つ戻しておく。
  • それ以外の場合：現在の文字 s[i] をスタックにプッシュする。
• 各ループの最後で i を 1 増やす。
• すべての処理が終わったら、スタック内の要素を連結して結果として返す。

Pythonでの実装例

class Solution:
    def solve(self, s):
        stack = []
        i = 0
        while i < len(s):
            if len(stack) and stack[-1] == s[i]:
                x = stack.pop()
                while i < len(s) and x == s[i]:
                    i += 1
                i -= 1
            else:
                stack.append(s[i])
            i += 1
        return "".join(stack)

ob = Solution()
s = "xyyyxxz"
print(ob.solve(s))

入力

"xyyyxxz"

出力

z

動作のポイント

このアルゴリズムの鍵は、スタックのトップと現在の文字を常に比較する点にあります。重複が見つかったタイミングで、その文字の連なり全体を一気にスキップできるため、同じ文字のかたまりをまとめて除去できます。内側の while ループを抜けた直後の「i -= 1」は、外側のループ末尾にある「i += 1」と相殺するための調整処理で、これによって次の未処理の文字から正しく再開できます。

計算量

時間計算量は O(n)、空間計算量も O(n) です（n は文字列の長さ）。各文字はスタックに対して最大でも 1 回のプッシュと 1 回のポップしか発生しないため、線形時間で処理が完了します。