1 回だけ出る最初の文字の位置｜コーディング面接問題

問題

英小文字だけでできた文字列 s を受け取ります。s の中で 1 回しか出ない文字を探し、そのうちいちばん前にある文字の位置 (0 から数えた番号) を返す関数を書いてください。

1 回しか出ない文字が無いときは -1 を返します
s の長さは 0 以上 10000 以下です

入力と出力の例

例 1

a と b は 2 回ずつ出ます。1 回だけの c は 3 番にあります。

入力

s = "aabcb"

出力

例 2

k と a は 2 回ずつ出るので、まん中の y が答えです。

入力

s = "kayak"

出力

例 3

どの文字も 2 回出るので、答えはありません。

入力

s = "xyzzyx"

出力

-1

面接での聞かれ方

面接では、短い一言で渡されることが多いです。

「文字列の中で、重ならない最初の文字の位置を返してください」
書き終えたあとに「いまの書き方の計算量は？」「もっと速くできますか？」と続けて聞かれます
「無いときは何を返しますか？」と、答えが無い場合を聞かれることもあります

位置を返すのか文字を返すのか、無いときに何を返すのかを、最初に確かめておきます。返す物が決まると、最後の 1 行で迷いません。

まず考える手順

段 1

まずは素直に、文字を前から 1 つずつ取り、その文字がほかの位置にもあるかを全部調べます。ほかに無ければ、それが答えです。これでも正しく動きますが、文字ごとに文字列全体を読み直すので、時間は O(n²) です。

段 2

何度も読み直しているのは、「この文字は全部で何回出るか」です。それなら、先に 1 回だけ全体を読んで、文字ごとの回数を辞書 (Python の dict、JavaScript の Map) に数えておけば足ります。

段 3

数え終えたら、もう 1 回前から読みます。今度は文字ごとに辞書の回数を見て、1 回の文字に初めて当たったら、その位置を返します。前から読んでいるので、最初に当たった物がいちばん前です。最後まで当たらなければ -1 を返します。

ここから解答です。先に自分で書いてから読むと、考え方が残ります。

解答

Python

def first_unique_index(s):
    count = {}
    for ch in s:
        seen = count.get(ch, 0)
        count[ch] = seen + 1
    for i, ch in enumerate(s):
        if count[ch] == 1:
            return i
    return -1

JavaScript

function firstUniqueIndex(s) {
  const n = s.length;
  const count = new Map();
  for (const ch of s) {
    const c = count.get(ch);
    count.set(ch, (c ?? 0) + 1);
  }
  for (let i = 0; i < n; i++) {
    if (count.get(s[i]) === 1) {
      return i;
    }
  }
  return -1;
}

1 回目で数え、2 回目で探します。2 回なめても、時間はどちらも O(n) のままです。

計算量

時間は O(n) です。文字列を 2 回読みますが、2 回は定数なので O(n) と書きます
使う記憶は、文字の種類の数だけです。英小文字なら多くても 26 種類なので、O(1) と見なせます
段 1 の、文字ごとに全体を読み直す書き方は、時間が O(n²)、記憶は O(1) です

よくある間違い

辞書の並びから答えを探す。 2 回目を辞書の中身で回すと、文字の位置が分かりません。位置を知るために、2 回目も元の文字列を前から読みます
1 回の読みで済ませようとする。読みながら「まだ 1 回しか出ていない文字」を答えにすると、あとで 2 回目が出てきたときに間違えます。例 2 の kayak で、最初の k を答えてしまいます
無いときの戻り値を書き忘れる。繰り返しを抜けたあとに -1 を返す行が無いと、Python は None、JavaScript は undefined を返します

面接での話し方の例

書き始める前に、方針を短く口に出します。

「文字ごとに全体を読み直せば O(n²) で解けます。ただ、知りたいのは文字ごとの回数なので、先に 1 回読んで辞書に数えておきます。そのあと前からもう 1 回読み、回数が 1 の文字に最初に当たった位置を返します。時間は O(n) です。」

書き終えたら、例を 1 つ手でたどって見せます。

「例 2 の kayak でたどります。1 回目で、k が 2 回、a が 2 回、y が 1 回と数えます。2 回目は前から見て、k も a も 2 回なので飛ばし、2 番の y が 1 回なので 2 を返します。」

解答を動かした版 Python 3.12.14Node.js 22.23.4確認日 2026年10月24日