Sliding window : faire glisser une fenêtre plutôt que tout recalculer

Le sliding window maintient une fenêtre contiguë (sous-tableau ou sous-chaîne) et la fait glisser : on ajoute un élément à droite et on retire un élément à gauche, plutôt que de tout recalculer depuis zéro à chaque position. Ça transforme souvent un O(n²) en O(n).

Fenêtre de taille fixe : utile quand l'énoncé donne une taille k explicite (ex : moyenne maximale d'un sous-tableau de taille k). On ajoute l'élément entrant et on retire l'élément sortant, chaque opération en O(1).

Fenêtre de taille variable : la fenêtre grandit tant qu'une condition est respectée, et rétrécit dès qu'elle est violée (ex : la plus longue sous-chaîne sans caractères répétés). C'est la variante la plus fréquente en entretien.

Signal pour reconnaître ce pattern : l'énoncé parle de « sous-tableau contigu » ou « sous-chaîne contiguë » et demande un maximum, un minimum, ou une condition à satisfaire. Si les éléments doivent rester contigus, sliding window est un candidat naturel — contrairement à un sous-ensemble quelconque, qui demanderait plutôt du backtracking.

Le pattern est souvent combiné avec un hashmap ou un compteur de fréquences pour suivre ce qu'il y a « dans la fenêtre », ce qui permet de savoir en O(1) si la condition est encore respectée quand la fenêtre bouge.

Quiz