Sliding window per le sottostringhe
Implementi una sliding window di dimensione variabile per trovare la sottostringa più lunga senza caratteri ripetuti e la finestra minima contenente tutti i caratteri cercati
Sliding window per le sottostringhe è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Il concetto di finestra scorrevole
Una finestra scorrevole mantiene un sottoarray (o una sottostringa) tra un puntatore sinistro e uno destro. Invece di ricalcolare da zero le proprietà di ogni possibile sottoarray in O(n²), la finestra si espande verso destra aggiungendo un elemento e si restringe da sinistra rimuovendone uno, mantenendo uno stato aggiornato in O(1) a ogni passaggio. Il risultato è un algoritmo O(n). La finestra viene definita «scorrevole» perché avanza nell'array senza tornare indietro.
# 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])Dimensione fissa o variabile della finestra
Esistono due varianti della finestra scorrevole. In una finestra di dimensione fissa, entrambi i puntatori avanzano allo stesso ritmo e la finestra contiene sempre esattamente k elementi. In una finestra di dimensione variabile, il puntatore destro si espande in modo avido e quello sinistro si sposta solo quando la finestra viola un vincolo. Le finestre di dimensione variabile risolvono problemi come «la sottostringa più lunga senza caratteri ripetuti», in cui la dimensione ottimale della finestra non è nota in anticipo.
# 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)) # 2Sottostringa più lunga senza ripetizioni
È il problema più noto sulle finestre scorrevoli a dimensione variabile. Utilizzi un set per tenere traccia dei caratteri presenti nella finestra corrente. Espanda la finestra verso destra; quando trova un duplicato, la restringa da sinistra finché il duplicato non viene rimosso. Una versione più veloce utilizza una hash map che memorizza l'ultimo indice di ogni carattere, consentendo al puntatore sinistro di saltare oltre il duplicato in un solo passaggio invece di avanzare di un carattere alla volta.
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')Sottostringa minima
Date le stringhe s e t, trovi la finestra più piccola in s che contenga tutti i caratteri di t. Utilizzi due mappe delle frequenze: need (caratteri richiesti) e have (caratteri nella finestra corrente che soddisfano il requisito). Tenga traccia del numero di caratteri distinti di t per i quali il requisito è soddisfatto (contatore formed). Espanda la finestra verso destra per includere i caratteri; quando tutti i caratteri di t sono coperti, la restringa da sinistra per ridurla al minimo. Tempo 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'Schema della finestra scorrevole
La maggior parte dei problemi con finestre scorrevoli a dimensione variabile segue uno schema comune: espandere la finestra verso destra per includere il nuovo carattere, aggiornare lo stato della finestra, verificarne la validità e, se non è valida, restringerla da sinistra finché non torna valida. L'idea fondamentale è che il puntatore sinistro si muove solo in avanti e non torna mai indietro; perciò il lavoro complessivo di tutti i passaggi di restringimento è O(n). La finestra visita ogni elemento al massimo due volte: una quando viene aggiunto e una quando viene rimosso.
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 bestPermutazione in una stringa
Verifichi se una qualsiasi permutazione del pattern p è presente come sottostringa di s. Verificare una permutazione equivale a cercare una finestra con la stessa frequenza dei caratteri di p. Mantenga una finestra scorrevole di esattamente len(p) caratteri e confronti i conteggi delle frequenze. Confrontare interi oggetti Counter a ogni passaggio costa O(26) (un valore costante per l'inglese minuscolo), quindi il costo complessivo è O(n × 26) = O(n).
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')) # FalseSottostringhe anagrammate: conta tutte
Trovi tutti gli indici iniziali degli anagrammi di p presenti in s. Si tratta della stessa tecnica a finestra fissa usata per il problema della permutazione in una stringa, ma invece di restituire True al primo riscontro, raccolga tutte le posizioni corrispondenti. La dimensione della finestra è fissa e pari a len(p); la faccia scorrere su s e confronti i conteggi delle frequenze a ogni passaggio.
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]Sottostringa più lunga con al massimo 2 caratteri distinti
Una variante della finestra scorrevole: trovi la sottostringa più lunga che contenga al massimo 2 caratteri distinti. Mantenga una mappa delle frequenze dei caratteri presenti nella finestra corrente. Quando la mappa contiene più di 2 voci, sposti il puntatore sinistro verso destra (decrementando la frequenza ed eliminando il carattere se arriva a zero) finché il vincolo non è nuovamente rispettato. Questo è un caso particolare del problema «al massimo k caratteri distinti», con 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')Massimo nella finestra scorrevole
Trovi il massimo in ogni finestra di dimensione k. Verificare con la forza bruta il massimo di ogni finestra richiede O(n×k). L'approccio ottimale utilizza una deque monotona di indici: mantenga una deque decrescente, in modo che il primo elemento sia sempre l'indice del massimo nella finestra corrente. Rimuova dal primo elemento gli indici che escono dalla finestra e dall'ultimo quelli precedenti quando entra un elemento più grande. Tempo complessivo 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]Quando usare la finestra scorrevole
Ricorra alla finestra scorrevole quando incontra:
- Sottostringhe o sottoarray con un vincolo (lunghezza massima, somma = k, al massimo k caratteri distinti)
- Finestre di dimensione fissa con un'operazione di aggregazione (massimo, somma, frequenza)
- Problemi su intervalli contigui (non su sottoinsiemi arbitrari)
# 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])) # 2Conteggio delle finestre valide: al massimo K
Alcuni problemi chiedono di contare i sottoarray che soddisfano una condizione. Un trucco utile consiste nel contare i sottoarray con al massimo k caratteri distinti e poi sottrarre per ottenere quelli con esattamente k: exactly(k) = at_most(k) - at_most(k-1). Ogni chiamata a at_most è O(n), per un totale di O(n). La funzione at_most conta le finestre in cui il numero di caratteri distinti non supera k sommando right - left + 1 (tutti gli indici sinistri validi per ogni indice destro).
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)) # 9Verifica rapida
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: la finestra scorrevole elimina il costo O(n²) mantenendo uno stato aggiornato della finestra, che viene modificato in O(1) quando gli elementi entrano ed escono, le finestre di dimensione fissa fanno avanzare entrambi i puntatori allo stesso ritmo, mentre quelle di dimensione variabile si espandono avidamente verso destra e si restringono a sinistra solo quando viene violato un vincolo e la sottostringa minima e la permutazione in una stringa utilizzano entrambe lo stato della finestra basato su mappe delle frequenze, con un contatore che tiene traccia del numero di caratteri richiesti attualmente soddisfatti. Prossimamente esploreremo gli anagrammi e le mappe delle frequenze dei caratteri.
Domande Frequenti
La lezione «Sliding window per le sottostringhe» è gratuita?
Sì — il testo completo di «Sliding window per le sottostringhe» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Sliding window per le sottostringhe»?
Implementi una sliding window di dimensione variabile per trovare la sottostringa più lunga senza caratteri ripetuti e la finestra minima contenente tutti i caratteri cercati Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Sliding window per le sottostringhe»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- API delle stringhe Python per i colloqui
- Sliding window per le sottostringhe
- Anagrammi e mappe delle frequenze dei caratteri
- Codifica, inversione e palindromi delle stringhe