Fenêtre glissante pour les sous-chaînes
Implémentez une fenêtre glissante de taille variable pour trouver la plus longue sous-chaîne sans caractères répétés et la fenêtre minimale contenant tous les caractères recherchés.
Fenêtre glissante pour les sous-chaînes est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
Le concept de fenêtre glissante
Une fenêtre glissante maintient un sous-tableau (ou une sous-chaîne) entre un pointeur gauche et un pointeur droit. Au lieu de recalculer les propriétés de chaque sous-tableau possible depuis zéro en O(n²), la fenêtre s'étend vers la droite en ajoutant un élément et se réduit vers la gauche en en retirant un, tout en maintenant un état courant en O(1) par étape. On obtient ainsi un algorithme en O(n). La fenêtre est dite « glissante » parce qu'elle avance dans le tableau sans revenir en arrière.
# Fixed-size window sum: O(n) after O(k) setup
def max_sum_window(nums, k):
window_sum = sum(nums[:k]) # initial window
best = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] # add new right
window_sum -= nums[i - k] # remove old left
best = max(best, window_sum)
return best
print(max_sum_window([2,1,5,1,3,2], 3)) # 9 ([5,1,3])Taille de fenêtre fixe ou variable
Il existe deux variantes de la fenêtre glissante. Dans une fenêtre de taille fixe, les deux pointeurs avancent au même rythme et la fenêtre contient toujours exactement k éléments. Dans une fenêtre de taille variable, le pointeur droit s'étend de manière gloutonne et le pointeur gauche ne réduit la fenêtre que lorsque celle-ci viole une contrainte. Les fenêtres de taille variable permettent de résoudre des problèmes comme celui de la « plus longue sous-chaîne sans caractères répétés », dont la taille optimale est inconnue à l'avance.
# Variable window: longest substring with at most k distinct chars
def longest_k_distinct(s, k):
from collections import defaultdict
freq = defaultdict(int)
left = 0
best = 0
for right in range(len(s)):
freq[s[right]] += 1
while len(freq) > k: # window invalid: shrink
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_k_distinct('eceba', 2)) # 3 ('ece')
print(longest_k_distinct('aa', 1)) # 2Plus longue sous-chaîne sans répétition
C'est le problème de fenêtre glissante variable le plus connu. Utilisez un ensemble pour suivre les caractères de la fenêtre actuelle. Étendez la fenêtre vers la droite ; lorsqu'un doublon est trouvé, réduisez-la depuis la gauche jusqu'à ce que le doublon soit supprimé. Une version plus rapide utilise une table de hachage contenant le dernier indice de chaque caractère, ce qui permet au pointeur gauche de sauter au-delà du doublon en une seule étape au lieu d'avancer progressivement.
def length_of_longest_substring(s):
char_idx = {} # char -> last seen index
left = 0
best = 0
for right, c in enumerate(s):
if c in char_idx and char_idx[c] >= left:
left = char_idx[c] + 1 # jump past duplicate
char_idx[c] = right
best = max(best, right - left + 1)
return best
print(length_of_longest_substring('abcabcbb')) # 3 ('abc')
print(length_of_longest_substring('bbbbb')) # 1
print(length_of_longest_substring('pwwkew')) # 3 ('wke')Sous-chaîne de fenêtre minimale
Étant données les chaînes s et t, trouvez la plus petite fenêtre de s contenant tous les caractères de t. Utilisez deux tables de fréquences : need (caractères requis) et have (caractères de la fenêtre actuelle qui satisfont la contrainte). Suivez le nombre de caractères distincts de t qui sont satisfaits (compteur formed). Étendez la fenêtre vers la droite pour inclure des caractères ; lorsque t est entièrement couvert, réduisez-la depuis la gauche pour minimiser la fenêtre. Complexité temporelle : O(|s| + |t|).
from collections import Counter
def min_window(s, t):
if not t or not s: return ''
need = Counter(t)
have = {}
formed = 0
required = len(need)
left = 0
best = float('inf'), 0, 0
for right, c in enumerate(s):
have[c] = have.get(c, 0) + 1
if c in need and have[c] == need[c]:
formed += 1
while formed == required:
if right - left + 1 < best[0]:
best = right - left + 1, left, right
have[s[left]] -= 1
if s[left] in need and have[s[left]] < need[s[left]]:
formed -= 1
left += 1
return s[best[1]:best[2]+1] if best[0] != float('inf') else ''
print(min_window('ADOBECODEBANC', 'ABC')) # 'BANC'Modèle de fenêtre glissante
La plupart des problèmes de fenêtre glissante variable suivent un modèle : étendre la fenêtre vers la droite pour inclure le nouveau caractère, mettre à jour l'état de la fenêtre, vérifier sa validité et, si elle est invalide, la réduire depuis la gauche jusqu'à ce qu'elle redevienne valide. L'idée essentielle est que le pointeur gauche avance uniquement vers l'avant — il ne recule jamais — et que le travail total de toutes les réductions est donc O(n). La fenêtre parcourt chaque élément au plus deux fois (une fois lors de son ajout, une fois lors de son retrait).
def sliding_window_template(s, condition_check, update_state, remove_state):
"""
Generic sliding window skeleton.
Adapt condition_check, update_state, remove_state per problem.
"""
left = 0
state = {} # or whatever state you need
best = 0
for right in range(len(s)):
update_state(state, s[right]) # expand window
while not condition_check(state): # window invalid
remove_state(state, s[left]) # shrink window
left += 1
best = max(best, right - left + 1)
return bestPermutation dans une chaîne
Vérifiez si une permutation du motif p existe comme sous-chaîne de s. Vérifier une permutation revient à rechercher une fenêtre ayant les mêmes fréquences de caractères que p. Maintenez une fenêtre glissante contenant exactement len(p) caractères et comparez les comptes de fréquences. Comparer des objets Counter entiers à chaque étape coûte O(26) (une constante pour les minuscules anglaises), soit O(n × 26) = O(n) au total.
from collections import Counter
def check_inclusion(p, s):
if len(p) > len(s): return False
need = Counter(p)
window = Counter(s[:len(p)])
if need == window: return True
for right in range(len(p), len(s)):
left = right - len(p)
window[s[right]] += 1
window[s[left]] -= 1
if window[s[left]] == 0:
del window[s[left]]
if window == need:
return True
return False
print(check_inclusion('ab', 'eidbaooo')) # True ('ba')
print(check_inclusion('ab', 'eidboaoo')) # FalseSous-chaînes anagrammes : tout compter
Trouvez tous les indices de début des anagrammes de p dans s. Il s'agit de la même technique de fenêtre fixe que pour le problème de la permutation dans une chaîne, mais au lieu de renvoyer True à la première correspondance, nous collectons toutes les positions correspondantes. La taille de la fenêtre est fixée à len(p) ; nous la faisons glisser sur s et comparons les comptes de fréquences à chaque étape.
from collections import Counter
def find_anagrams(s, p):
result = []
need = Counter(p)
k = len(p)
window = Counter(s[:k])
if window == need:
result.append(0)
for right in range(k, len(s)):
window[s[right]] += 1
left_char = s[right - k]
window[left_char] -= 1
if window[left_char] == 0:
del window[left_char]
if window == need:
result.append(right - k + 1)
return result
print(find_anagrams('cbaebabacd', 'abc')) # [0, 6]Plus longue sous-chaîne avec au plus 2 caractères distincts
Voici une variante de la fenêtre glissante : trouvez la plus longue sous-chaîne contenant au plus 2 caractères distincts. Maintenez une table de fréquences des caractères de la fenêtre actuelle. Lorsque la table contient plus de 2 entrées, déplacez le pointeur gauche vers la droite (diminuez la fréquence, puis supprimez l'entrée si elle atteint zéro) jusqu'à ce que la contrainte soit de nouveau respectée. Il s'agit d'un cas particulier du problème « au plus k caractères distincts », avec k=2.
def longest_substring_two_distinct(s):
from collections import defaultdict
freq = defaultdict(int)
left = 0
best = 0
for right, c in enumerate(s):
freq[c] += 1
while len(freq) > 2:
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_substring_two_distinct('eceba')) # 3 ('ece')
print(longest_substring_two_distinct('ccaabbb')) # 5 ('aabbb')Maximum d'une fenêtre glissante
Trouvez le maximum dans chaque fenêtre de taille k. Une vérification par force brute du maximum de chaque fenêtre coûte O(n×k). L'approche optimale utilise une file monotone à double extrémité d'indices : maintenez une file décroissante afin que son début contienne toujours l'indice du maximum de la fenêtre actuelle. Retirez du début les indices qui sortent de la fenêtre, puis retirez de la fin les indices lorsqu'un élément plus grand entre dans la fenêtre. La complexité temporelle totale est O(n).
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Maintain decreasing order
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1: # window is full
result.append(nums[dq[0]])
return result
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]Quand utiliser la fenêtre glissante
Utilisez la fenêtre glissante lorsque vous rencontrez :
- une sous-chaîne ou un sous-tableau soumis à une contrainte (longueur maximale, somme = k, au plus k caractères distincts)
- une taille de fenêtre fixe avec une agrégation (maximum, somme, fréquence)
- des questions portant sur une plage contiguë (et non sur des sous-ensembles arbitraires)
# Recognising sliding window problems:
# 1. Fixed window: 'maximum average of subarray of length k'
def max_avg(nums, k):
s = sum(nums[:k])
best = s
for i in range(k, len(nums)):
s += nums[i] - nums[i-k]
best = max(best, s)
return best / k
print(max_avg([1,12,-5,-6,50,3], 4)) # 12.75
# 2. Variable window: 'smallest subarray with sum >= target'
def min_sub_len(target, nums):
left = s = 0
best = float('inf')
for right, n in enumerate(nums):
s += n
while s >= target:
best = min(best, right - left + 1)
s -= nums[left]; left += 1
return 0 if best == float('inf') else best
print(min_sub_len(7, [2,3,1,2,4,3])) # 2Compter les fenêtres valides : au plus K
Certains problèmes demandent le nombre de sous-tableaux qui satisfont une condition. Une astuce utile consiste à compter les sous-tableaux contenant au plus k caractères distincts, puis à soustraire pour obtenir exactement k : exactly(k) = at_most(k) - at_most(k-1). Chaque appel à at_most coûte O(n), soit O(n) au total. La fonction at_most compte les fenêtres dans lesquelles le nombre de caractères distincts ne dépasse pas k, en additionnant right - left + 1 (tous les points de départ gauches valides pour chaque position droite).
from collections import defaultdict
def subarrays_at_most_k(s, k):
freq = defaultdict(int)
left = 0
count = 0
for right, c in enumerate(s):
freq[c] += 1
while len(freq) > k:
freq[s[left]] -= 1
if freq[s[left]] == 0: del freq[s[left]]
left += 1
count += right - left + 1 # all valid windows ending at right
return count
def subarrays_exactly_k(s, k):
return subarrays_at_most_k(s, k) - subarrays_at_most_k(s, k-1)
print(subarrays_exactly_k('araaci', 2)) # 9Vérification rapide
Vérifiez votre compréhension des concepts de Structures de données et algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris que : la fenêtre glissante élimine O(n²) en maintenant l'état courant d'une fenêtre, mis à jour en O(1) lorsque les éléments y entrent et en sortent, les fenêtres de taille fixe font avancer les deux pointeurs au même rythme ; les fenêtres de taille variable s'étendent gloutonnement vers la droite et se réduisent vers la gauche uniquement lorsqu'une contrainte est violée, et la sous-chaîne de fenêtre minimale et la permutation dans une chaîne utilisent toutes deux l'état d'une fenêtre fondé sur une table de fréquences, avec un compteur qui suit le nombre de caractères requis actuellement satisfaits. Nous allons maintenant étudier les anagrammes et les tables de fréquences de caractères.
Questions Fréquemment Posées
La leçon « Fenêtre glissante pour les sous-chaînes » est-elle gratuite ?
Oui — le texte complet de « Fenêtre glissante pour les sous-chaînes » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Fenêtre glissante pour les sous-chaînes » ?
Implémentez une fenêtre glissante de taille variable pour trouver la plus longue sous-chaîne sans caractères répétés et la fenêtre minimale contenant tous les caractères recherchés. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « Fenêtre glissante pour les sous-chaînes » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- API des chaînes Python pour les entretiens
- Fenêtre glissante pour les sous-chaînes
- Anagrammes et tables de fréquences de caractères
- Codage, inversion et palindromes de chaînes