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回、eは1回（インデックス8）現れます。しかし、yも1回（インデックス4）現れ、こちらのほうが先なので、答えは4です。
- 入力
- s = "swiss"
- 出力
- 1
- 説明
swissでは、文字sが3回現れます。インデックス1の文字wは1回現れ、インデックス2のiも同様です。最初に現れるほうが選ばれるので、答えは1です。
- 入力
- s = "aabbcc"
- 出力
- -1
- 説明
aabbccの各文字は2回ずつ現れるため、一意な文字はなく、答えは-1です。
提出時に隠しテスト+17件
発展問題
文字がストリームから1つずつ到着し、そのたびに、これまでの最初の一意な文字を報告する必要があります。答えを常に最新の状態に保つには、どうすればよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ある文字が1回だけ現れるかどうかを知るには、その前にある文字だけでなく、文字列全体を見る必要があります。
文字は26文字しかありません。
sに各文字が何回出現するかが分かっていれば、どの位置についても定数時間で答えられるでしょうか？2回に分けて処理します。1回目では、26個のカウンターの配列を使って、各文字の出現回数を数えます。2回目では、文字列を左から順にたどり、出現回数が1の文字が見つかったら、その最初のインデックスを返します。最後までたどっても見つからない場合は、
-1を返します。
解説
たどり着いたときには固有に見える文字でも、文字列の最後にもう一度現れることがあるため、左から右へ一度眺めるだけでは不十分です。まずすべての文字を数え、次にもう一度調べることで、各位置の文字が固有かどうかを定数時間で判定できます。
各文字の2つ目のコピーを探す
正しいが、最大のテストでは終わらない
考え方
左から順に位置を確認します。位置 i について、文字列全体を調べ、同じ文字を持つ別の位置 j を探します。見つからなければ、s[i] は一意であり、左から順に進んでいるので、これが最初の一意な文字です。i を返します。coddycode では、位置 0 から 3 までの各文字はそれぞれ別の場所にも見つかり、位置 4 の y は見つかりません。
調べる範囲は、i より前と後の両方を含め、文字列全体にする必要があります。文字列の前のほうに同じ文字があれば、後ろのほうにある場合と同様、その文字は対象外になります。
最初に同じ文字が見つかった時点で調べるのをやめれば、ほとんどの文字列では効率的ですが、すべての場合に当てはまるわけではありません。各文字が長い連続列になっている場合、たとえば 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個のカウンターを持つ配列ですべての出現数を保持できます。インデックス0はa、インデックス25はzに対応します。文字のインデックスは、その文字コードからaの文字コードを引いた値です。
最初の走査でカウンターを埋めます。coddycodeの場合、カウンターは c: 2、o: 2、d: 3、y: 1、e: 1となります。2回目の走査では文字列を左からたどり、文字の出現数が1である最初の位置で止まります。それはインデックス4のyです。質問は最初の位置についてであり、アルファベット順で最初の文字についてではないため、2回目の走査では26個のカウンターではなく、文字列をたどる必要があります。
どちらの走査も文字列を一度ずつ読むため、時間計算量は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
落とし穴と境界ケース
ほとんどの間違いは、判断を早まったり、2回目の走査で誤ったものを調べたりすることで起こります。
- 位置
iより前の文字だけを確認する。abcaでは最初のaより前に同じ文字はありませんが、それでも一意ではありません。 - 2回目の走査で文字列ではなくカウンター配列を走査する。
baでは、最初に値が 1 となるカウンターはaに対応しますが、答えはインデックス 0、つまりbです。 - インデックスではなく文字を返したり、インデックスを1始まりで返したりする。Lua と R は1から数えるため、返す前に1を引いてください。
-1の場合を忘れる。aabbccのような文字列には一意な文字がありませんが、ループの後も関数は値を返さなければなりません。- 文字コードをそのまま使ってカウンターをインデックス指定する。
aは 97 なので、26要素の配列の範囲を大きく超えます。まずaの文字コードを引いてください。
よくある質問4
「文字列中の最初の一意な文字」の時間計算量はどれくらいですか？
文字数を数えてから文字列を走査する処理は、それぞれ n ステップの2回の走査なので、時間計算量は O(n) です。26個のカウンターは長さに関係なく同じ領域を使用するため、追加の空間計算量は O(1) です。
文字列を1回走査するだけで解けますか？
はい。1回の走査で、各文字について最初に現れた位置のインデックスを保存するか、再び現れたときに重複として記録します。その後、26文字を確認し、1回だけ現れた文字の中で最小のインデックスを選びます。文字列の読み取りは1回だけで、最後の確認にかかるのは26ステップです。
文字を数えるには、ハッシュマップと配列のどちらを使うべきでしょうか？
小文字だけの場合、26個のカウンターを持つ配列はハッシュマップよりも小さく、高速です。Unicodeテキストのように、文字列にあらゆる文字を含められる場合は、ハッシュマップが適切な選択です。アルゴリズムは同じです。まず数え、次に文字列を走査します。
2回目のパスでは、なぜカウントではなく文字列を走査するのですか？
カウントからわかるのは、どの文字が重複していないかだけで、それらがどこにあるかはわかりません。答えは文字列の中で最初に現れる重複していない文字なので、文字列を順番にたどり、カウントが1の文字がある最初の位置で止まる必要があります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def firstUniqChar(s):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
s = "coddycode"
期待値
4