First Unique Character in a String
小文字の英字からなる文字列 s が与えられます。文字列全体でちょうど1回だけ現れる最初の文字を見つけ、そのインデックスを0から数えて返してください。すべての文字が2回以上現れる場合は、-1 を返してください。
関数
- sstring
- 検索する文字列（小文字のみ）
- 戻り値integer
- ちょうど1回だけ現れる最初の文字のインデックス。該当する文字がない場合は -1
制約
1 ≤ s.length ≤ 5 × 104sには小文字の英字（aからzまで）のみが含まれます。
例
- 入力
- s = "coddycode"
- 出力
- 4
- 説明
coddycodeでは、cとoは2回、dは3回現れます。y（インデックス4）とe（インデックス8）はどちらも1回現れ、yが先に現れるため、答えは4です。
- 入力
- s = "swiss"
- 出力
- 1
- 説明
- 文字
sは3回現れます。インデックス1のwとインデックス2のiはどちらも1回現れ、wのほうが先に現れます。
- 入力
- s = "aabbcc"
- 出力
- -1
- 説明
aabbccの各文字は2回ずつ現れるため、答えは-1です。
発展問題
文字がストリームから1つずつ届きます。それぞれ届くたびに、その時点までの最初の一意な文字をどのように報告しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ある文字が一度だけ現れるかどうかを知るには、その文字より前の文字だけでなく、文字列全体を見る必要があります。
文字は全部で26個しかありません。
sに各文字が何回出現するかを知っていれば、どの位置についても定数時間で答えられるでしょうか？2回走査します。1回目は、26個のカウンターの配列で各文字の出現回数を数えます。2回目は、文字列を左から順に調べ、出現回数が1の文字の最初のインデックスを返します。最後まで調べても見つからない場合は、
-1を返します。
解説
たどり着いたときには他にないように見える文字でも、文字列の最後で繰り返されることがあるため、左から右への一度の確認だけでは不十分です。まずすべての文字を数えれば、2回目の走査で各位置の文字が一意かどうかを一定時間で判定できます。
各文字の2つ目のコピーを探す
正しいが、最大のテストでは終わらない
考え方
左から各位置について、文字列全体を調べ、同じ文字を持つ別の位置がないか確認します。両側を調べます。前にある重複も、後にある重複と同じように、その文字を候補から除外します。重複がない最初の位置が答えです。coddycodeでは、位置0から3はそれぞれ重複が見つかり、インデックス4のyには重複がありません。
各文字が1つの長い連続区間にある場合、最初の重複が見つかった時点で止めても役に立ちません。たとえば、aが2000個続き、次にbが2000個続く、といった場合、各走査は前のすべての区間を通り過ぎます。n = 5 × 10^4では、比較回数は10億回を超えます。
アルゴリズム
- 左から右へ、各インデックス
iについて: i以外のすべてのインデックスjを調べ、s[j]がs[i]と等しい最初のインデックスで停止します。- そのような
jが存在しない場合は、iを返します。 - すべてのインデックスでコピーが見つかった場合は、
-1を返します。
def firstUniqChar(s):
n = len(s)
for i in range(n):
repeated = False
for j in range(n): # look for another copy of s[i]
if j != i and s[j] == s[i]:
repeated = True
break
if not repeated:
return i
return -1文字を数えてから、スキャンする
考え方
位置ごとに再検索するのではなく、各文字を一度ずつ数えます。文字は26種類しかないため、26個のカウンターですべての出現回数を保持でき、文字のコードからaのコードを引いた値をインデックスにします。
最初のパスでカウンターを埋めます。coddycodeの場合、最後にカウントが1になるのはyとeだけです。2回目のパスでは文字列を左からたどり、カウントが1の最初の文字、つまりインデックス4のyで停止します。nステップを2回行うため、時間計算量はO(n)で、どの長さの文字列でも26個のカウンターの空間計算量はO(1)です。
アルゴリズム
- 26 個のゼロからなる配列を作成します。
sの各文字について、そのカウンターに 1 を加えます。- インデックス 0 から
sをもう一度たどります。文字の出現回数が 1 である最初のインデックスを返します。 - 最後までたどって見つからなければ、
-1を返します。
def firstUniqChar(s):
counts = [0] * 26 # counts[0] is 'a', counts[25] is 'z'
for ch in s:
counts[ord(ch) - ord("a")] += 1
for i, ch in enumerate(s):
if counts[ord(ch) - ord("a")] == 1:
return i
return -1
落とし穴と境界ケース
- 位置
iより前の文字だけを確認すること。abcaでは最初のaより前に同じ文字はありませんが、それでも一意ではありません。 - 2回目の走査で文字列ではなくカウンター配列をたどること。
baでは、値が 1 の最初のカウンターはaに対応しますが、答えのインデックスは 0 です。 - 文字コードをそのまま使ってカウンターをインデックス指定すること。
aは 97 なので、26 個のカウンターの範囲を大きく超えています。 - インデックスではなく文字を返すこと、または Lua や R で 1 始まりのインデックスを返すこと。
よくある質問3
文字列中の最初の一意な文字の時間計算量はどれくらいですか？
文字を数えてから文字列を走査するのは、それぞれnステップの2回の処理なので、実行時間はO(n)です。26個のカウンターは長さに関係なく同じ領域を使うため、追加領域はO(1)です。
文字列を1回走査するだけで解けますか？
はい。一度の走査で、各文字について最初に現れた位置のインデックスを保存するか、再び現れたときに重複として印を付けます。次に、一度だけ現れた26文字の中で最小のインデックスを求めます。文字列を読み取るのは一度だけで、最後の確認にかかるのは26ステップです。
文字を数えるには、ハッシュマップと配列のどちらを使うべきでしょうか？
小文字だけの場合、26個のカウンターを持つ配列のほうが小さく、高速です。Unicodeテキストなど、文字列に任意の文字が含まれる場合は、ハッシュマップが適切な選択です。アルゴリズムは同じです。カウントしてから、文字列を走査します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def firstUniqChar(s):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
s = "coddycode"
期待される出力
4