Zenn
🧵

JavaScriptで解くLeetCode：Longest Substring Without Repeating Characters

2024/12/27に公開
JavaScript
LeetCode
tech

このシリーズでは、プログラミング学習サイト LeetCode に掲載されている問題の中から良問を厳選し、JavaScript を使って解説していきます。

この記事では、Arai60に収録されているLongest Substring Without Repeating Characters を、スライドウィンドウ法 (Sliding Window) の手法を使って解く方法を解説します。

1. 問題について

  • 入力: 文字列 s
  • 出力:
    • s の中で、同じ文字が重複しない 連続した部分（＝部分文字列）のうち、一番長いものの「長さ」を求める

例

s = "abcabcbb"
  • abc → 長さ 3
  • bca → 長さ 3
  • cab → 長さ 3
  • …
    最長 3 となる。

部分文字列: 元の文字列から「連続する形」で切り出した文字列のこと
（例） "abc" は "zabcx" の部分文字列だけど、"ac" は飛び飛びなので違う

2. スライドウィンドウ法とは

2.1 ウィンドウを動かすイメージ

  1. ウィンドウ (枠)
    • いま見ている「重複なしの部分文字列」を、スタート地点とエンド地点で挟んだイメージ。
  2. 右端を1文字ずつ進める
    • 新しい文字をウィンドウに入れてみる。
  3. 重複があったら、左端を進める
    • 同じ文字が2回出たら、左端を移動させて、重複が消えるようにする。

2.2 ポインタは2つ

  1. start
    • ウィンドウの左端（重複なし部分文字列の始まり）
  2. i
    • ループ変数。ウィンドウ右端を順に広げていく。

2.3 どこで重複したかわかるように記録

  • オブジェクト（連想配列）usedChar を作って、各文字が「最後に登場した位置 (index)」を記憶。
    • もし次に同じ文字が出てきたら、前回の位置 を確認して、そこを基準に start を動かす。

3. 実際のコード

function lengthOfLongestSubstring(s) {
  let maxLen = 0;        // 最長の長さを記録
  let start = 0;         // 重複なしの部分文字列が始まる位置
  const usedChar = {};   // 文字が最後に出現した位置を覚える

  for (let i = 0; i < s.length; i++) {
    const currentChar = s[i];

    // もしこの文字が既に出現していて、
    // その出現位置が start の後ろ(または同じ)なら、start を動かす
    if (
      usedChar[currentChar] !== undefined &&
      usedChar[currentChar] >= start
    ) {
      // 重複をなくすため、start を「重複文字の次の位置」に移動
      start = usedChar[currentChar] + 1;
    }

    // この文字が出現した最新位置を更新
    usedChar[currentChar] = i;

    // ウィンドウのサイズ = (i - start + 1)
    const windowSize = i - start + 1;
    if (windowSize > maxLen) {
      maxLen = windowSize;
    }
  }

  return maxLen;
}

4. 処理の流れ（イメージ）

例: s = "abcabcbb"

  1. はじめ

    • start = 0, maxLen = 0
    • usedChar = {} (空)

  2. i = 0 → 文字 "a"

    • usedChar["a"] は未定義 → 重複なし
    • 記録： usedChar["a"] = 0
    • ウィンドウサイズ = (0 - 0 + 1) = 1 → maxLen = 1

  3. i = 1 → 文字 "b"

    • 未定義 → 重複なし
    • usedChar["b"] = 1
    • ウィンドウサイズ = (1 - 0 + 1) = 2 → maxLen = 2

  4. i = 2 → 文字 "c"

    • 未定義 → usedChar["c"] = 2
    • ウィンドウサイズ = (2 - 0 + 1) = 3 → maxLen = 3

  5. i = 3 → 文字 "a"

    • usedChar["a"] = 0 だが、0 >= start(0) → 重複認定
    • start = 0 + 1 = 1 に移動
    • 更新： usedChar["a"] = 3
    • ウィンドウサイズ = (3 - 1 + 1) = 3 → maxLen = 3 (変わらず)

… という流れで、最終的に maxLen = 3 となり、重複のない部分文字列の最長は 3 とわかります。

5. スライドウィンドウ法の利点

  1. 高速: 各文字を一度ずつ見るだけで OK → O(n)
  2. わかりやすい: 「右端を進めて、重複があったら左端を進める」の繰り返し
  3. メモリ少なめ: usedChar というオブジェクト1つだけ管理

6. まとめ

  • 「Longest Substring Without Repeating Characters」は、同じ文字を二度使わない連続部分 の長さを求める問題。
  • スライドウィンドウ法なら、重複が起きたときに start をサッと移動させる だけで解決。
  • コードはシンプルで、処理速度も O(n) と速い！

「連続区間を探す」タイプの問題では、このスライドウィンドウの考え方がとても役立ちます。

ぜひ、ほかの問題でも使ってみてください！

Discussion