Sliding window : faire glisser une fenêtre

Dès qu'un énoncé parle de sous-tableau ou sous-chaîne contigu, on fait glisser une fenêtre au lieu de tout recalculer.

On ajoute l'élément qui entre à droite et on retire celui qui sort à gauche : O(1) par déplacement, O(n) au total.

Taille fixe : somme maximale de k éléments#

function maxSumWindow(nums: number[], k: number): number {
  let window = 0;
  for (let i = 0; i < k; i++) window += nums[i];
  let best = window;
  for (let i = k; i < nums.length; i++) {
    window += nums[i] - nums[i - k];                // entre à droite, sort à gauche
    best = Math.max(best, window);
  }
  return best;
}

Taille variable : plus longue sous-chaîne sans répétition#

On garde l'index de la dernière apparition de chaque caractère ; si le caractère est déjà dans la fenêtre, on remonte le bord gauche juste après.

function longestUnique(s: string): number {
  const last = new Map<string, number>();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const seenAt = last.get(s[right]);
    if (seenAt !== undefined && seenAt >= left) left = seenAt + 1;
    last.set(s[right], right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Astuce : si les éléments doivent rester contigus, pensez sliding window ; s'il s'agit d'un sous-ensemble quelconque, c'est plutôt du backtracking ou de la DP. On combine souvent la fenêtre avec un hashmap de fréquences pour savoir en O(1) si elle est encore valide.