スライディング ウィンドウ手法を使用した、繰り返し文字を含まない最長の部分文字列

ソリューションのステップを詳しく見て、各ステップがどのように機能するかを見てみましょう

次の入力を受け取ったと仮定します:

見つかった文字を格納する空のセットと、見つかった最長の部分文字列を保持する変数を作成します。

ここで、right が指す値がセット内に存在するかどうかを確認します。存在しない場合は、セットに追加し、右に 1 つ先に進みます。その後、セットのサイズをlongSubstr変数に格納されている値と比較して、最長の部分文字列を更新します。

右が指す値がセット内にあるかどうかを確認します。そうでないことがわかったので、それをセットに追加し、右に 1 ずつインクリメントします。その後、セットのサイズと longSubstr の値の間の最大値を取得します。

right が指す値がセット内にあるかどうかを確認します。つまり、c がセット内にないことを意味します。したがって、それをセットに追加し、右に 1 ずつ増分して、最大部分文字列を確認します。

ここで、right が指す値 (a) がセット内に存在するかどうかを確認します。そうなっていることがわかったので、セットからそれを削除し、左に 1 歩前に移動します。

右が指す値は b であり、集合内に存在します。

したがって、左ポインタを 1 つ前に移動し、セットから b を削除します。

これで、b がセット内にあることがわかりました。そのため、left が指す値を削除し、左に 1 ステップ前進します。

右が指す値は c であり、集合内に存在します。
したがって、それをセットから削除し、左に 1 つ前に移動します。

同じ手法を ステップ 17 まで続けて、次の結果が得られます:

これは JavaScript の実装です

function longestSubstring(s) {
  let left = 0
  let right = 0

  let maxSubstr = 0
  let set = new Set()

  while (right < s.length) {
    const currentChar = s[right]

    if (!set.has(currentChar)) {
      set.add(currentChar)
      right++
      maxSubstr = Math.max(maxSubstr, right - left) // Update max substring length
    } else {
      set.delete(s[left])
      left++
    }
  }

  return maxSubstr
}

let inputString = 'abcabcbb'
console.log(longestSubstring(inputString)) // Output: 3 ("abc")

以上がスライディング ウィンドウ手法を使用した、繰り返し文字を含まない最長の部分文字列の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。