Pythonで文字列内の最初のユニーク文字を見つける方法

文字列が与えられたとき、その中で最初に一度だけ出現する文字（ユニークな文字）を見つける問題を考えてみましょう。

例えば、文字列が "people" の場合、出現回数が1回である最初の文字は 'o' です。この場合、そのインデックスである 2 を返します。もし該当する文字が文字列中に存在しない場合は、-1 を返します。

解法のアプローチ

この問題は、以下の手順で効率的に解くことができます。

• 頻度マップ（辞書）を作成する
• 文字列内の各文字 c について処理を行う：
  • c が頻度マップに存在しない場合は、キーとして追加し値を 1 に設定する
  • すでに存在する場合は、そのカウントを +1 する
• 作成した頻度マップを走査し、値が 1 になっているキー（文字）が見つかれば、そのインデックスを返す
• 最後まで見つからなければ -1 を返す

このアルゴリズムの計算量は、文字列を2回走査するため O(n) となり、非常に効率的です。

実装例

それでは、実際のコード実装を見てみましょう。

class Solution(object):
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        frequency = {}
        for i in s:
            if i not in frequency:
                frequency[i] = 1
            else:
                frequency[i] += 1
        for i in range(len(s)):
            if frequency[s[i]] == 1:
                return i
        return -1

ob1 = Solution()
print(ob1.firstUniqChar("people"))
print(ob1.firstUniqChar("abaabba"))

入力例

"people"
"abaabba"

出力結果

2
-1

コードの解説

まず、空の辞書 frequency を用意し、1回目のループで各文字の出現回数を記録します。次に、2回目のループで元の文字列を先頭から順に確認し、対応する文字の出現回数が1であれば、その時点のインデックスを即座に返します。

2つ目の入力例 "abaabba" の場合、すべての文字（a と b）が複数回出現するため、ユニークな文字は存在せず、-1 が出力されます。