Substring Terpanjang Tanpa Mengulang Aksara dengan Teknik Tetingkap Gelongsor

Mari kita pecahkan langkah penyelesaian dan lihat cara setiap langkah berfungsi

Kami menganggap kami menerima input berikut:

Kami akan mencipta set kosong untuk menyimpan huruf yang kami temui dan pembolehubah untuk mengekalkan subrentetan terpanjang yang kami temui.

Sekarang, kami akan menyemak sama ada nilai yang ditunjukkan oleh kanan wujud dalam set. Jika ia tidak wujud, kami akan menambahnya pada set dan bergerak ke kanan satu langkah ke hadapan. Selepas itu, kami akan mengemas kini subrentetan terpanjang dengan membandingkan saiz set dengan nilai yang disimpan dalam pembolehubah longSubstr.

Kami akan menyemak sama ada nilai yang ditunjukkan oleh kanan berada dalam set. Kami melihat bahawa ia tidak, jadi kami menambahnya pada set dan menambah tepat sebanyak 1. Selepas itu, kami mengambil maksimum antara saiz set dan nilai dalam longSubstr.

Kami menyemak sama ada nilai yang ditunjuk oleh kanan berada dalam set, bermakna c tiada dalam set. Jadi, kami menambahkannya pada set, naikkan tepat sebanyak 1 dan semak subrentetan maksimum.

Sekarang, kami menyemak sama ada nilai yang ditunjuk ke kanan, iaitu a, wujud dalam set. Kami melihatnya, jadi kami mengeluarkannya dari set dan bergerak ke kiri selangkah ke hadapan.

Nilai yang ditunjuk oleh kanan ialah b, dan ia wujud dalam set.

Oleh itu, kami menggerakkan penunjuk kiri satu langkah ke hadapan dan mengeluarkan b daripada set.

Sekarang kita melihat bahawa b berada dalam set, jadi kita mengalih keluar nilai yang ditunjuk oleh kiri dan bergerak ke kiri selangkah ke hadapan.

Nilai yang ditunjuk oleh kanan ialah c, dan ia wujud dalam set.
Oleh itu, kami mengeluarkannya dari set dan bergerak ke kiri selangkah ke hadapan.

Kami akan meneruskan teknik yang sama sehingga langkah 17 dan akan mendapat:

Berikut ialah pelaksanaan 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")

Atas ialah kandungan terperinci Substring Terpanjang Tanpa Mengulang Aksara dengan Teknik Tetingkap Gelongsor. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!