Pythonで文字列内の最初の繰り返し文字のインデックスを検索する方法

文字列 s が与えられたとき、その中で最初に繰り返し出現する文字のインデックスを求める問題を考えてみましょう。繰り返し文字がひとつも存在しない場合は、-1 を返します。

例えば、入力が "abcade" の場合、出力は 3 になります。これは、文字 'a' がインデックス 3 の位置に再び現れているためです。

解法のアプローチ

この問題を解くには、以下の手順に従います。

• 文字の出現履歴を記録するための辞書（マップ）chars を定義します。
• i を 0 から文字列の長さまで順にループさせます。
  • s[i] がすでに chars に存在する場合、その時点のインデックス i を返します。
  • 存在しない場合は、chars[s[i]] のカウントを 1 増やして記録します。
• ループが終了しても繰り返し文字が見つからなければ、-1 を返します。

このアルゴリズムの計算量は O(n) で、文字列を一度走査するだけで答えが得られるため、非常に効率的です。

実装例

それでは、以下のPythonコードを見て、実際の動作を確認してみましょう。

from collections import defaultdict

class Solution:
    def solve(self, s):
        chars = defaultdict(int)
        for i in range(len(s)):
            if s[i] in chars:
                return i
            else:
                chars[s[i]] += 1
        return -1

ob = Solution()
print(ob.solve("abcade"))

入力

"abcade"

出力

3

collections.defaultdict を使うことで、キーが存在しない場合でも自動的に初期値 0 が設定されるため、コードを簡潔に書くことができます。通常の辞書を使う場合は dict.get() メソッドなどで同様の処理を実装することも可能です。