Pythonで特定の文字列から重複する文字を削除するプログラム

文字列 s が与えられたとします。ここから、すでに一度出現したことのある重複文字をすべて削除する必要があります。ただし、最終的な文字列は元の文字列と同じ文字の出現順序を保たなければなりません。

この問題は、順序付き辞書（OrderedDict）を使って文字の挿入順序を維持することで効率的に解決できます。辞書の値には各文字の出現回数を格納しますが、今回の目的では頻度の値そのものは重要ではありません。辞書が完成したら、キーを順番に取り出して連結するだけで、重複のない文字列が得られます。

例えば、入力が s = "bbabcaaccdbaabababc" の場合、出力は "bacd" になります。

アルゴリズム

• d := キーが挿入順に保存される辞書を作成する
• 文字列 s 内の各文字 c について、以下を繰り返す
  • c が d に存在しない場合は d[c] := 0 を設定する
  • d[c] := d[c] + 1 として出現回数をカウントする
• キーを挿入順に連結して出力文字列を作成し、返す

実装例

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

from collections import OrderedDict

def solve(s):
    d = OrderedDict()
    for c in s:
        if c not in d:
            d[c] = 0
        d[c] += 1

    return ''.join(d.keys())

s = "bbabcaaccdbaabababc"
print(solve(s))

入力

"bbabcaaccdbaabababc"

出力

"bacd"

補足

なお、Python 3.7 以降では通常の dict も挿入順序を保持することが仕様で保証されているため、OrderedDict を使わずに同じ結果を得ることも可能です。また、この手法の計算量は O(n) であり、文字列の長さに対して線形時間で処理できるため、大きなデータでも高速に動作します。