重複なし最長部分文字列｜コードで実践

重複なし最長部分文字列

このレッスンで分かること

重複なし最長部分文字列は「窓を伸ばせるだけ伸ばす + 重複が出たら縮める」可変長スライド窓の典型問題

見た目は単純ですが、O(n^2) の全部分文字列をチェックする素朴な解は O(n^3) にもなり得るので、効率化が大切な問題です

文字列 s の中で「同じ文字が二度以上現れない連続した部分文字列」の最大の長さを求めます

重複なし最長部分文字列とは

文字列内で重複文字を含まない連続した部分文字列の最大長を、可変長スライディングウィンドウで O(n) で求める。

文字列 s の中で「同じ文字が二度以上現れない連続した部分文字列」の最大の長さを求めます。例えば s = "abcabcbb" なら答えは 3 ("abc")、s = "bbbbb" なら 1 ("b")、s = "pwwkew" なら 3 ("wke") です。

見た目は単純ですが、O(n^2) の全部分文字列をチェックする素朴な解は O(n^3) にもなり得るので、効率化が大切な問題です。LeetCode などの 超頻出問題 で、可変長スライディングウィンドウの代表例として知られています。

重複なし最長部分文字列は「窓を伸ばせるだけ伸ばす + 重複が出たら縮める」可変長スライド窓の典型問題。

可変長スライディングウィンドウとは

前のレッスンで扱った「固定長のスライド窓」と違い、本問では 窓のサイズが状況に応じて伸び縮みします。

右端 (right) を 1 つ進めて新しい文字を窓に追加
もし新しい文字が 窓内にすでに含まれている なら、左端 (left) を進めて重複を取り除く
重複がなくなった時点での窓の長さで最大値を更新

この「伸ばすだけ伸ばし、ダメになったら左を縮める」発想は、文字列だけでなく配列問題でも頻出します。

図で動きを追う

diagram (will load when visible)

Python の実装

Python

def longestUniqueSubstring(s):
    seen = set()
    left = 0
    best = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        if right - left + 1 > best:
            best = right - left + 1
    return best

ポイントは set を使って「現在の窓に含まれる文字」を高速に管理することです。s[right] in seen は O(1) で判定でき、合計の計算量は O(n) に収まります (left と right がそれぞれ最大 n 回しか動かないため)。

JavaScript の実装

JavaScript

function longestUniqueSubstring(s) {
  const seen = new Set();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left += 1;
    }
    seen.add(s[right]);
    if (right - left + 1 > best) best = right - left + 1;
  }
  return best;
}

JavaScript の Set は Python の set とほぼ同じ感覚で扱えます。seen.has() で確認、seen.add() で追加、seen.delete() で削除。

計算量の分析

ぱっと見では while ループの中に外側の for があるので O(n^2) に見えるかもしれませんが、内側の while は left を進めるだけで、left は 0 から n までしか進めません。つまり全体を通して内側ループの総実行回数も 最大 n 回。right も n 回。合わせて O(n) です。これは アモーティズド分析 (償却計算量) の典型例です。

ループの中にループがあっても、全体としての操作回数を合計すれば O(n) に収まることがある。これがアモーティズド分析の威力。

よくある間違い

1 つ目は 辞書 (map) を使って indices を覚えておこうとする実装 がやや複雑になりがちな点です。{ char: index } を持つ方法もあって 1 ステップで left をジャンプできて高速ですが、本問では理解しやすさ重視で set を使います。

2 つ目は 窓のサイズ計算 で right - left と書いてしまうケースです。窓は [left, right] の閉区間で長さは right - left + 1 です。+1 を忘れると最大長が 1 小さくなります。

3 つ目は 空文字 や 1 文字 の入力で best = 0 のまま返してしまうケースです。1 文字なら最大長は 1 になるはずです。上記コードは for ループ内で必ず best を更新するので、1 文字入力では 1 が返ります。

やってみよう

"abcabcbb" を手で追ってみる。right = 3 (a) で衝突が起きて left が動く挙動を確認する。
"dvdf" で答えが 3 ("vdf") になることを確認する。left がどう動くか観察しよう。
set ではなく dict (Python) / Map (JS) を使って、left = max(left, lastIndex[char] + 1) というジャンプ方式に書き換えてみる。これは内側の while を消せる別解。

可変長スライド窓は、文字列・配列の「条件を満たす最長」「最短」「個数」を求める問題で頻出。形を覚えておけば応用は無限大。

よくある質問

Q. このトピックは実務でどう役立ちますか？

A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。

Q. 計算量はどう求めれば良いですか？

A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。

Q. 覚えるべき定番アルゴリズムは何ですか？

A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。

次のレッスン

次は 大きな数の文字列乗算 で、巨大な整数を文字列として扱い、桁ごとの筆算アルゴリズムで掛け算を実装する方法を学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

最長部分文字列の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 最長部分文字列とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

重複なし最長部分文字列