Pythonで文字列内の連続した重複文字を削除する方法

ここでは、「R」と「L」のみで構成された文字列 s を扱います。目標は、連続する「R」および連続する「L」が一切存在しない状態にするために、削除する文字数を最小限に抑えることです。

たとえば、入力が "LLLRLRR" の場合、出力は LRLR となります。

解決の手順

この問題を解決するには、以下の手順に従います。

• 変数 seen に文字列の最初の文字を代入します。
• 変数 ans にも文字列の最初の文字を代入します。
• インデックス1以降の各文字 i について以下を繰り返します。
  • i が seen と異なる場合：
    • ans に i を追加します。
    • seen を i で更新します。
• 最後に ans を返します。

つまり、直前の文字と同じ文字はスキップし、異なる文字だけを結果に追加していくことで、隣接する重複をすべて取り除くことができます。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

class Solution:
    def solve(self, s):
        seen = s[0]
        ans = s[0]
        for i in s[1:]:
            if i != seen:
                ans += i
                seen = i
        return ans
ob = Solution()
print(ob.solve("LLLRLRR"))

入力

"LLLRLRR"

出力

LRLR

処理のポイント

このアルゴリズムは、文字列を一度だけ走査すればよいため、時間計算量は O(n)、追加で必要となるメモリも結果文字列分のみで O(n) です。前の文字を記憶しておき、同じ文字が続く間は無視するというシンプルな発想で、「RLRL...」のような交互パターンを効率的に生成できます。同様の考え方は、一般的な重複圧縮やデータクレンジングの処理にも応用できます。