【Python】文字ストリームから最初に一度だけ現れる文字を検索する方法

文字ストリーム（あるいは単純な文字列）が与えられ、その中から最初に一度だけ出現する文字を見つける問題を考えてみましょう。例えば、文字列が「people」の場合、出現回数が1回となる最初の文字は「o」であり、そのインデックス 2 を返します。該当する文字が存在しない場合は -1 を返します。

解法のアプローチ

この問題は、各文字の出現回数を記録する「頻度マップ（ハッシュマップ）」を使うことで効率的に解けます。手順は以下のとおりです。

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

実装例

以下のPythonコードは、上記のアルゴリズムを実装したものです。

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

1つ目の例「people」では、最初に一度だけ現れる文字「o」の位置である 2 が出力されます。一方、「abaabba」ではすべての文字が複数回出現するため、-1 が返されます。

計算量の分析

• 時間計算量：O(n) — 文字列を2回走査しますが、それぞれ線形時間なので、全体としても O(n) で処理できます。
• 空間計算量：O(k) — k は文字列中の異なる文字の種類数です。英小文字のみを扱う場合は最大26個のため、実質的には定数 O(1) とみなせます。

このように、頻度マップを活用することで、文字ストリームや長い文字列に対しても高速に最初の非反復文字を特定できます。データストリームのように文字が逐次届くケースでは、頻度マップを更新しながら随時チェックすることで同様のロジックが応用可能です。