【Python】文字列から重複した文字を削除して一意な文字列を生成する方法

文字列 s が与えられたとき、それまでに出現したことのある文字を取り除き、各文字が1回だけ現れるように圧縮した文字列を返すことを考えます。この問題は、挿入順序を保持できる「順序付き辞書(OrderedDict)」を使うことで、シンプルかつ効率的に解くことができます。

辞書の値には各文字の出現回数(頻度)を格納しますが、今回の目的にとって頻度そのものは重要ではありません。重要なのは「どの文字が最初に登場したか」という順序の情報です。辞書が完成したら、キーを順番に取り出して連結するだけで、求める文字列が得られます。

例えば、入力が s = "cabbbaadac" の場合、出力は "cabd" となります。2回目以降に出現した文字(b、a、c など)はすべて除外され、初回出現時の順序だけが残ります。

解法のアルゴリズム

以下の手順で問題を解きます。

• キーが挿入された順序を保持する辞書 d を用意します。
• 文字列 s の各文字 c について、次の処理を行います。
  • c がまだ辞書 d に存在しない場合は、d[c] = 0 として登録します。
  • d[c] の値を1増やします(頻度のカウント)。
• すべての文字を処理し終えたら、辞書のキーを先頭から順に連結した文字列を作成して返します。

実装例(Python)

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

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 = "cabbbaadac"
print(solve(s))

入力

"cabbbaadac"

出力

cabd

補足：より簡潔な書き方(dict.fromkeys)

Python 3.7 以降では通常の dict も挿入順序を保持するため、次のように dict.fromkeys() を使えば1行で同じ結果が得られます。

def solve(s):
    return ''.join(dict.fromkeys(s))

print(solve("cabbbaadac"))  # 出力: cabd

どちらの方法でも計算量は O(n)(n は文字列の長さ)となり、非常に高速に動作します。