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

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

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

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

ここで、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 




          

            
        

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