問題
文字列 s をs の
- 「続いた部分」なので、
文字を 飛ばして 拾った 物は 数えません。 "abcb"からa、c、bを飛ばして 拾った "acb"は使えません - 大文字と
小文字は 別の 文字です。 空白や 記号も 1 つの 文字として数えます sは空の こともあります。 その ときは 0 を返します sの長さは 0 以上 50000 以下で、 英字、 数字、 記号、 空白 (ASCII の 文字) だけで できています
入力と出力の例
例 1
"toky" と "kyot" がo か t が 2 回出てきます。
入力
s = "tokyoto"出力
4例 2
右の a は、a とb のa は"ab" か "ba" の 2 です。
入力
s = "abba"出力
2例 3
空の
入力
s = ""出力
0面接での聞かれ方
スライディングウィンドウの
- 「文字列の
中で、 同じ 文字を 含まない 最長の 部分文字列の 長さを 返してください」 - 最初に
条件を 確かめると 評価が 上がります。 「部分文字列は 続いた 部分ですか、 飛ばしても よいですか？」 「空の 文字列は 来ますか？」 「文字の 種類は 何ですか、 英小文字だけですか？」の 3 つは 聞いておきます - 書き終えた
あとに、 次のような 続きが よく 来ます - 「長さではなく、
その 部分 その ものを 返してください」 (左の 端と 長さを 覚えておけば 済みます) - 「同じ
文字を k 回まで 許すなら？」 「違う 文字が k 種類までなら？」 (窓の 中の 数を 数える 辞書に 替えます) - 「使う
記憶を 文字の 種類で 言うと？」 (記憶は O(min(n, m))、 m は 文字の 種類の 数、と 答えます)
- 「長さではなく、
- 「全部試す
書き方から、 どうやって 速くしましたか？」と、 考えの 筋を 順に 聞かれる こともあります
ミドルの"abba" のような
アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。
まず
段 1
まずは
段 2
左のleft とright をright - left + 1 を
段 3
新しい
段 4
ただし、"abba" で、a をa は 0 です。
解答
Python
Python
def longest_unique_substring(s):
last = {}
left = 0
best = 0
for r in range(len(s)):
c = s[r]
p = last.get(c, -1)
if p >= left:
left = p + 1
last[c] = r
size = r - left + 1
best = max(best, size)
return bestJavaScript
JavaScript
function longestUniqueSubstring(
s
) {
const last = new Map();
const n = s.length;
let left = 0;
let best = 0;
for (let r = 0; r < n; r++) {
const c = s[r];
const p = last.get(c) ?? -1;
if (p >= left) {
left = p + 1;
}
last.set(c, r);
const size = r - left + 1;
best = Math.max(best, size);
}
return best;
}Go
Go
func longestUniqueSubstring(
s string,
) int {
last := map[byte]int{}
left := 0
best := 0
for r := 0; r < len(s); r++ {
c := s[r]
p, ok := last[c]
if ok && p >= left {
left = p + 1
}
last[c] = r
best = max(best, r-left+1)
}
return best
}last には、p >= left で
計算量
- 時間は O(n) です。
右の 端は 1 回ずつ 進み、 左の 端は 一気に 飛ぶだけで 戻らないので、 1 文字あたり決まった 数の 手間で済みます - 使う
記憶は O(min(n, m)) です。 m は 文字の 種類の 数 (ASCII なら 128) で、 辞書には 種類の 数より 多くは 入りません。 文字の 種類が 決まっているので、 O(1) と 言ってもかまいません - 段 1 の
全部試す 書き方は O(n × k) で、 文字の 種類に 上限が 無ければ O(n²) でした。 左の 端を 戻さない ことで、 1 重の 繰り返しに できました
よく
- 前に
出た 位置が 窓の 中かを 確かめずに飛ばす。 辞書に ある 文字なら 必ず left = last[c] + 1と書くと、 例 2 の "abba"で最後の aを見た とき、 左の 端が 2 から 1 へ 戻り、 "bba"を同じ 文字の 無い窓と 数えて 3 を 返します。 いちばん 多い 間違いです - 重なりが
出たら 窓を 空に して、 いまの 文字から 数え直す。 "cbcd"では、2 つ目の cで数え直すと "cd"の 2 しか見つからず、 本当の 答えの "bcd"の 3 を逃します。 縮めるのは 前の 同じ 文字の 1 つ右まで、です - 長さを
right - leftで数える。 両端を含めるので + 1が要ります。 1 文字の "x"で 1 になるかを 確かめると 気づけます - 最長を、
重なりが 出た ときだけ比べる。 最後まで 重なりが 出ない "abcdef"のような文字列では、 一度も 比べずに 0 が 返ります。 毎回比べます - 英小文字だけと
決めつけて、 長さ 26 の 配列を使う。 空白や 数字が 来ると、 位置の 計算がは み出します。 最初に 文字の 種類を 確かめ、 分からなければ 辞書を使います - 飛ばして
拾った 並び (部 分列) と 取り違える。 部分列なら 答えは 「違う文字の種類の数」に なり、 まったく 別の 問題です。 最初に 「続いた部分ですか？」と 確かめます
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「全部の
開始位置から 伸ばすと、 文字の 種類に 上限が 無ければ O(n²) です。 左右の 端を 持つ窓に して、 窓の 中に 同じ 文字が 無い 状態を 保ちます。 各文字が 最後に 出た 位置を 辞書に 覚えて おき、 重なりが 出たら 左の 端を その 1 つ右へ 飛ばします。 ただし前に 出た 位置が 窓の 外なら 飛ば さず、 左の 端を 戻さないようにします。 時間は O(n)、 記憶は 文字の 種類の 数までです。」
書き終えたら、
「
"abba"でたどります。 a、bと伸ばして 長さ 2 です。 次の bは位置 1 に あったので、 左の 端を 2 へ 飛ばします。 最後の aは位置 0 に ありましたが、 0 + 1 の 1 は いまの 左の 端 2 より 左なので、 左の 端は 2 のままです。 窓は "ba"で長さ 2、 答えは 2 です。」