Längster Teilstring ohne sich wiederholende Zeichen mit der Sliding-Window-Technik

Lassen Sie uns die Lösungsschritte aufschlüsseln und sehen, wie jeder Schritt funktioniert

Wir gehen davon aus, dass wir folgende Eingabe erhalten haben:

Wir erstellen einen leeren Satz, um die Buchstaben zu speichern, auf die wir gestoßen sind, und eine Variable, um die längste Teilzeichenfolge zu speichern, die wir gefunden haben.

Jetzt prüfen wir, ob der Wert, auf den rechts zeigt, in der Menge vorhanden ist. Wenn es nicht existiert, fügen wir es der Menge hinzu und gehen einen Schritt nach rechts weiter. Danach aktualisieren wir den längsten Teilstring, indem wir die Größe des Satzes mit dem in der Variablen longSubstr gespeicherten Wert vergleichen.

Wir prüfen, ob der Wert, auf den rechts zeigt, in der Menge enthalten ist. Wir sehen, dass dies nicht der Fall ist, also fügen wir es zur Menge hinzu und erhöhen es um 1 nach rechts. Danach nehmen wir das Maximum zwischen der Größe der Menge und dem Wert in longSubstr.

Wir prüfen, ob der Wert, auf den right zeigt, in der Menge ist, was bedeutet, dass c nicht in der Menge ist. Also fügen wir es der Menge hinzu, erhöhen es um 1 nach rechts und überprüfen die maximale Teilzeichenfolge.

Jetzt prüfen wir, ob der Wert, auf den rechts zeigt, also a, in der Menge vorhanden ist. Wir sehen, dass dies der Fall ist, also entfernen wir es aus dem Set und gehen einen Schritt nach links nach vorne.

Der Wert, auf den rechts zeigt, ist b, und er existiert in der Menge.

Deshalb bewegen wir den linken Zeiger einen Schritt nach vorne und entfernen b aus der Menge.

Jetzt sehen wir, dass b in der Menge ist, also entfernen wir den Wert, auf den left zeigt, und gehen einen Schritt nach links vorwärts.

Der Wert, auf den rechts zeigt, ist c und existiert in der Menge.
Deshalb entfernen wir es aus dem Set und gehen einen Schritt nach links nach vorne.

Wir werden mit der gleichen Technik bis Schritt 17 fortfahren und erhalten:

Hier ist eine JavaScript-Implementierung

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")

Das obige ist der detaillierte Inhalt vonLängster Teilstring ohne sich wiederholende Zeichen mit der Sliding-Window-Technik. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!