Sous-chaîne la plus longue sans caractères répétitifs avec la technique de la fenêtre coulissante

Décomposons les étapes de la solution et voyons comment chaque étape fonctionne

Nous supposons que nous avons reçu la contribution suivante :

Nous allons créer un ensemble vide pour stocker les lettres que nous avons rencontrées et une variable pour conserver la sous-chaîne la plus longue que nous avons trouvée.

Maintenant, nous allons vérifier si la valeur pointée à droite existe dans l'ensemble. S'il n'existe pas, nous l'ajouterons à l'ensemble et avancerons d'un pas. Après cela, nous mettrons à jour la sous-chaîne la plus longue en comparant la taille de l'ensemble à la valeur stockée dans la variable longSubstr.

Nous vérifierons si la valeur pointée à droite est dans l'ensemble. Nous voyons que ce n'est pas le cas, nous l'ajoutons donc à l'ensemble et incrémentons de 1 à droite. Après cela, nous prenons le maximum entre la taille de l'ensemble et la valeur dans longSubstr.

Nous vérifions si la valeur pointée par droite est dans l'ensemble, ce qui signifie que c n'est pas dans l'ensemble. Nous l'ajoutons donc à l'ensemble, incrémentons de 1 et vérifions la sous-chaîne maximale.

Maintenant, on vérifie si la valeur pointée par droite, qui est a, existe dans l'ensemble. Nous voyons que c'est le cas, alors nous le retirons de l'ensemble et avançons d'un pas vers la gauche.

La valeur pointée à droite est b, et elle existe dans l'ensemble.

Par conséquent, nous déplaçons le pointeur gauche d'un pas vers l'avant et supprimons b de l'ensemble.

Maintenant, nous voyons que b est dans l'ensemble, nous supprimons donc la valeur pointée par la gauche et avançons d'un pas vers la gauche.

La valeur pointée à droite est c, et elle existe dans l'ensemble.
Par conséquent, nous le retirons de l'ensemble et avançons d'un pas vers la gauche.

Nous continuerons avec la même technique jusqu'à étape 17 et obtiendrons :

Voici une implémentation 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")

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!