【Python入門】文字列の中から最初の繰り返しのない文字を見つける2つの方法

この記事では、文字列や文字のストリームの中から最初に現れる繰り返しのない文字（ユニークな文字）を見つける方法を解説します。この問題には複数のアプローチがあり、本稿では同じ文字列に対して2つの異なるプログラムを作成して比較してみます。

方法1：関数と辞書を使う方法（O(n)アルゴリズム）

まずは、辞書（dict）を使って各文字の出現回数をカウントし、出現順序も保持する効率的な関数ベースの方法です。

def firstNonRepeatingChar(str1):
    char_order = []
    counts = {}
    for c in str1:
        if c in counts:
            counts[c] += 1
        else:
            counts[c] = 1
            char_order.append(c)
    for c in char_order:
        if counts[c] == 1:
            return c
    return None

print(firstNonRepeatingChar('PythonforallPythonMustforall'))
print(firstNonRepeatingChar('tutorialspointfordeveloper'))
print(firstNonRepeatingChar('AABBCC'))

実行結果

M
u
None

このプログラムの計算量はO(n)であり、非常に効率的です。処理の流れは以下の通りです。

1. まず文字列を一度だけループで走査します。
2. 初めて見つかる文字であれば、counts辞書に値「1」で登録し、同時にchar_orderリストに出現順に追加します。
3. すでに存在する文字が出てきた場合は、countsの値を1ずつ増やしていきます。
4. 最後にchar_orderを順番に確認し、カウントが「1」の文字が見つかった時点でそれを返します。

すべての文字が繰り返しを含む場合（例：「AABBCC」）は、Noneが返される点にも注目してください。

方法2：whileループとreplace()を使う方法

次に、より直感的なアプローチとして、whileループと文字列のreplace()メソッドを組み合わせた方法を紹介します。

s = "tutorialspointfordeveloper"
while s != "":
    slen0 = len(s)
    ch = s[0]
    s = s.replace(ch, "")
    slen1 = len(s)
    if slen1 == slen0 - 1:
        print("最初の繰り返しのない文字は: ", ch)
        break
else:
    print("ユニークな文字が見つかりませんでした！")

実行結果

最初の繰り返しのない文字は:  u

このプログラムでは、先頭の1文字を取り出して文字列全体から削除し、削除前後の長さを比較しています。長さがちょうど1だけ減っていれば、その文字は1回しか出現していなかったことになるため、それが答えとなります。

まとめ

実務ではパフォーマンスを考慮して方法1のO(n)アルゴリズムを採用するのが一般的です。ただし、小規模な文字列や学習目的であれば、方法2のようなシンプルな実装も理解しておくと良いでしょう。