Guppi StudioPROBLEM 05
最初に1度だけ現れる文字
文字列の中で重複しない最初の文字位置を返します。
ログの識別子を表す文字列から、全体で1度だけ現れる最初の文字を探します。
firstUniqChar(value) はその位置を返し、該当する文字がなければ -1 を返してください。
例
入力: "aabbcdeed"
出力: 4
理由: 位置4の "c" が、左から最初の出現回数1の文字入力: "aabbcc"
出力: -1
理由: すべての文字が2回ずつ現れるため、条件を満たす文字がない制約
1 <= value.length <= 200,001- 入力は英小文字からなる
- 目標: O(n) 相当（文字ごとに残り全体を調べ直す解法は性能テストで時間切れになります）
対応する問題: LeetCode #387 First Unique Character in a String
まず素朴に解くと — 文字ごとに全体を数え直す
「この文字は何回出てくるか」を、その都度全体を調べて確かめる書き方です。
function firstUniqChar(value: string): number {
for (let i = 0; i < value.length; i += 1) {
let count = 0;
for (let j = 0; j < value.length; j += 1) {
if (value[j] === value[i]) count += 1;
}
if (count === 1) return i;
}
return -1;
}外側と内側で文字列全体を走るので O(n²) です。indexOf と lastIndexOf が一致するかを調べる書き方も、内部で同じ探索をしているため同じ計算量になります。
どこが遅いのか
性能テストは 200,001 文字（aaa…bbb…z）で、答えは末尾にあります。O(n²) 解はおよそ 400億回 の文字比較が必要で、到底終わりません。
問題は、同じ文字の出現回数を何度も数え直していることです。a が10万個あれば、a の回数を10万回計算しています。
発想の転換
数え直すのをやめて、1周目で全部数えておく。
ここで効くのが「走査を2回に分ける」考え方です。左から1回見るだけでは「この先にもう一度出てくるか」は分かりません。未来の情報が必要なら、先に1周して情報を集め、2周目で答えを探す。2回走っても O(n) + O(n) = O(n) のままです。
「1パスで無理なら2パス」は、配列・文字列の問題で何度も使える定番の型です。
解答例 — O(n)
function firstUniqChar(value: string): number {
const counts = new Map<string, number>();
for (const char of value) {
counts.set(char, (counts.get(char) ?? 0) + 1);
}
for (let i = 0; i < value.length; i += 1) {
if (counts.get(value[i]) === 1) return i;
}
return -1;
}2周目で 元の文字列を順番に 走るのが要点です。Map の並び順ではなく文字列の位置順で探すので、「最初の」という条件が自然に満たされます。
動きを追う — “aabbcdeed”
1周目の結果: a→2, b→2, c→1, d→2, e→2
2周目:
| i | value[i] | counts | 判定 |
|---|---|---|---|
| 0 | a | 2 | 次へ |
| 1 | a | 2 | 次へ |
| 2 | b | 2 | 次へ |
| 3 | b | 2 | 次へ |
| 4 | c | 1 | → 4 を返す |
計算量の比較
| 解法 | 時間 | 追加領域 | n = 200,001 での目安 |
|---|---|---|---|
| 文字ごとに数え直す | O(n²) | O(1) | 約400億比較 |
| 2パス + 頻度 Map | O(n) | O(k)（k = 異なる文字数、ここでは最大26） | 約40万操作 |
追加領域が「文字列長」ではなく「異なる文字の種類数」で抑えられる点も説明できると強いです。英小文字のみなら k ≤ 26 なので、実質 O(1) の領域と言えます。
面接でどう話すか
「1回の走査では未来の出現が分からないので、2パスにします。1周目で文字の頻度を Map に集め、2周目で文字列の先頭から頻度1の文字を探して位置を返します。時間は O(n)、追加領域は文字種類数なので英小文字なら定数です。」
「なぜ2パスにするのか」を先に言語化してから書き始めると、行き当たりばったりではない設計だと伝わります。
STEPWISE HINTS
ヒント
01最初の一手
左から見ただけでは、その文字が後でもう一度現れるか分かりません。情報を集める走査と、答えを探す走査を分けます。
02処理の組み立て
Map で各文字の出現回数を数えます。その後、元の順番で回数が1の文字を探します。
03コードの形
1回目のループで counts[char] を増やす。2回目のループで counts[value[i]] === 1 なら i を返す。なければ -1。
AFTER ACCEPTED
解説
まずは自分の言葉で方針を説明し、コードに落としてみましょう。