Minimum Window Substring
Ti vengono date due stringhe, s e t. Trova la sottostringa più corta di s che contiene ogni carattere di t, contando anche le ripetizioni: se t contiene una lettera due volte, la sottostringa deve contenerla almeno due volte. L'ordine non è importante e possono esserci anche altri caratteri.
Se ci sono più sottostringhe della stessa lunghezza minima, restituisci quella più a sinistra. Se nessuna contiene tutti i caratteri di t, restituisci una stringa vuota.
Funzione
- sstring
- la stringa da cercare
- tstring
- i caratteri che la finestra deve contenere, comprese le ripetizioni
- Restituiscestring
- la sottostringa più corta e, in caso di parità, più a sinistra di s che contiene tutti i caratteri di t, oppure una stringa vuota
Vincoli
1 ≤ s.length ≤ 5 × 1041 ≤ t.length ≤ 104setcontengono solo lettere inglesi. Le lettere maiuscole e minuscole sono caratteri diversi.- Quando diverse sottostringhe sono le più corte, la risposta è quella più a sinistra; quando non ne esiste nessuna, è
"".
Esempi
- Input
- s = "mappingtheplan"t = "nap"
- Output
- "plan"
- Spiegazione
- La prima finestra da sinistra che contiene una
n, unaae unapèappin, cinque caratteri.planle contiene tutte e tre in quattro caratteri, e nessuna sequenza di tre le contiene.
- Input
- s = "banana"t = "aan"
- Output
- "ana"
- Spiegazione
trichiede due copie diae unan.anaall'indice 1 contiene esattamente questo. Una secondaanainizia all'indice 3 e vince quella più a sinistra.
- Input
- s = "Coddy"t = "cd"
- Output
- ""
- Spiegazione
- La
CinCoddyè maiuscola, un carattere diverso dac. Nessuna sottostringa contiene unacminuscola, quindi la risposta è la stringa vuota.
Per approfondire
Quando t usa poche lettere e s è lunga, la maggior parte di s non conta mai. Riesci a fare in modo che la finestra salti solo tra le posizioni che contengono una lettera di t?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Una finestra che contiene tutto
tcontinua a contenerlo anche quando la allunghi, e una finestra a cui manca qualcosa continua a esserne priva anche quando la accorci. Usa questo per evitare di provare ogni inizio con ogni fine.Sposta in avanti un bordo destro finché la finestra non copre
t. Poi sposta in avanti il bordo sinistro finché la finestra continua a copriret, registrandola ogni volta. Nessuno dei due bordi deve mai spostarsi indietro.Tieni una tabella di quante altre copie di ogni carattere servono alla finestra e un numero,
missing, che indica quante copie mancano in totale. Un carattere che entra riducemissingsolo se era ancora necessario, e un carattere che esce lo aumenta solo se la finestra non ne contiene abbastanza. La finestra copretesattamente quandomissingè 0.
Soluzione
Contano solo le quantità nella finestra, non il loro ordine. Sposta il bordo destro finché la finestra include t, poi il bordo sinistro finché continua a includerlo; nessuno dei due bordi torna indietro. Un contatore dei caratteri mancanti ti dice in un solo passaggio se la finestra include t.
Fai crescere una finestra da ogni punto di partenza
Corretto, ma non termina sui test più grandi
Intuizione
Fissa un punto di partenza e amplia la finestra di un carattere alla volta, tenendo il conto di ogni carattere. Dopo ogni passaggio, controlla ciascuna delle u lettere usate da t. Il primo punto finale che soddisfa la condizione fornisce la finestra più corta che copre tutte le lettere a partire da questo punto, quindi fermati lì. I punti di partenza vengono esaminati da sinistra a destra e solo una finestra strettamente più corta sostituisce la migliore, quindi, in caso di parità, viene mantenuta quella più a sinistra.
Se non esiste alcuna finestra, ogni punto di partenza arriva fino alla fine di s: circa n²/2 passaggi, 1.25 × 10^9 per n = 5 × 10^4.
Algoritmo
- Conta quante volte compare ciascuna lettera richiesta da
t. - Per ogni
start, azzera una tabella dei conteggi e spostaendverso destra, aggiungendos[end]. - Quando la finestra contiene un numero sufficiente di ogni lettera, tienila se è strettamente più corta della migliore e passa allo start successivo.
- Restituisci la finestra migliore, oppure
""se nessuna coprivat.
def minWindow(s, t):
need = [0] * 128 # copies of each character code that t asks for
for ch in t:
need[ord(ch)] += 1
letters = [c for c in range(128) if need[c] > 0]
best_start, best_len = 0, len(s) + 1
for start in range(len(s)):
have = [0] * 128 # counts inside s[start..end]
for end in range(start, len(s)):
have[ord(s[end])] += 1
if all(have[c] >= need[c] for c in letters):
# The first end that covers t gives the shortest window from this start.
if end - start + 1 < best_len:
best_start, best_len = start, end - start + 1
break
if best_len > len(s):
return ""
return s[best_start:best_start + best_len]Finestra scorrevole che controlla ogni lettera
Intuizione
Aggiungere caratteri a una finestra che contiene ciò che cerchiamo fa sì che continui a contenerlo, mentre rimuovere caratteri da una finestra a cui manca qualcosa fa sì che continui a mancarle. Quindi, man mano che l'inizio si sposta a destra, la fine della finestra più corta che contiene ciò che cerchiamo non si sposta mai a sinistra.
Nessuna finestra viene tralasciata. Prendi la finestra migliore, da L a R. Perché left superi L prima che right raggiunga R, una finestra più corta che parte da L dovrebbe contenere t. Quindi, quando right raggiunge R, la riduzione porta left fino a L e registra la finestra.
Ogni estremo si sposta al massimo n volte, ma ogni controllo legge fino a u conteggi: O(n·u).
Algoritmo
- Conta le occorrenze richieste da
t; impostaleft = 0e la lunghezza migliore an+1. - Per ogni
right, aggiungis[right]ai conteggi della finestra. - Finché ogni lettera di
tè presente in quantità sufficiente, registra la finestra se è strettamente più corta, rimuovis[left]e fai avanzareleft. - Restituisci la finestra migliore, oppure
""se la lunghezza migliore è ancoran+1.
def minWindow(s, t):
need = [0] * 128 # copies of each character code that t asks for
for ch in t:
need[ord(ch)] += 1
letters = [c for c in range(128) if need[c] > 0]
have = [0] * 128 # counts inside s[left..right]
def covers():
for c in letters:
if have[c] < need[c]:
return False
return True
left = 0
best_start, best_len = 0, len(s) + 1
for right in range(len(s)):
have[ord(s[right])] += 1 # expand on the right
while covers(): # shrink from the left while the window still covers t
if right - left + 1 < best_len:
best_start, best_len = left, right - left + 1
have[ord(s[left])] -= 1
left += 1
if best_len > len(s):
return ""
return s[best_start:best_start + best_len]Finestra scorrevole con un contatore di elementi mancanti
Intuizione
Sostituisci la scansione con un unico numero. Sia need[c] il numero di copie di c richieste da t meno le copie presenti nella finestra; un valore negativo indica copie in eccesso. Sia missing il numero di copie che mancano ancora nella finestra, inizializzato alla lunghezza di t. La finestra contiene esattamente t quando missing è 0.
Un carattere che entra mentre il suo need è maggiore di 0 riempie una lacuna, quindi missing diminuisce. Un carattere la cui rimozione porta need a un valore maggiore di 0 crea una lacuna, quindi missing aumenta. Le copie in eccesso non lo modificano mai. In banana, con t = aan, missing raggiunge per la prima volta 0 in bana, e rimuovere la b in eccesso lascia ana, che continua a contenere la sequenza richiesta.
Ogni carattere entra ed esce una volta, a costo costante: tempo O(n + m), con una tabella di 128 conteggi.
Algoritmo
- Riempi
needcon il numero di occorrenze dit; impostamissingalla lunghezza dit,left = 0e la lunghezza migliore an+1. - Per ogni
right: seneed[s[right]]è maggiore di 0, diminuiscimissing; poi diminuiscineed[s[right]]. - Mentre
missingè 0, registra la finestra se è strettamente più corta. Aumentaneed[s[left]]; se ora è maggiore di 0, aumentamissing. Spostaleftin avanti. - Restituisci la finestra migliore, oppure
""se la lunghezza migliore è ancoran+1.
def minWindow(s, t):
# need[c]: copies of c that t asks for minus copies inside the window.
# Positive means the window still lacks c; negative means it holds spares.
need = [0] * 128
for ch in t:
need[ord(ch)] += 1
missing = len(t) # characters of t the window does not cover yet
left = 0
best_start, best_len = 0, len(s) + 1
for right in range(len(s)):
c = ord(s[right])
if need[c] > 0: # this copy fills a gap
missing -= 1
need[c] -= 1
while missing == 0: # the window covers t: record it, then shrink
if right - left + 1 < best_len:
best_start, best_len = left, right - left + 1
c = ord(s[left])
need[c] += 1
if need[c] > 0: # gave away a copy t needs
missing += 1
left += 1
if best_len > len(s):
return ""
return s[best_start:best_start + best_len]
Trappole e casi limite
- Contare le lettere invece delle occorrenze.
t = aanrichiede duea, quindibannon è sufficiente. - Modificare
missingper ogni carattere che entra o esce. In questo modo viene conteggiata unaain più emissingpuò arrivare a 0 mentre nella finestra manca lan. - Sostituire la finestra migliore in caso di lunghezza uguale. Nel secondo esempio, così si restituisce
anaall'indice 3. - Usare
ncome lunghezza per «non trovato». Quando la risposta è tuttas, anche la sua lunghezza èn; parti dan+1. - Una tabella di 26 posizioni indicizzate da
c - 'a'. Le lettere maiuscole, come nel terzo esempio, non rientrano nell'intervallo.
Domande frequenti3
Qual è la complessità temporale di Minimum Window Substring?
La finestra del contatore delle occorrenze mancanti viene eseguita in tempo O(n + m), dove n e m sono le lunghezze di s e t. La costruzione della tabella legge t una volta e ogni carattere di s entra ed esce dalla finestra al massimo una volta. La memoria aggiuntiva è un conteggio per ogni codice carattere.
Perché il bordo sinistro non si sposta mai indietro?
Il bordo sinistro supera una posizione solo dopo che la finestra che inizia lì ha coperto t, e quella finestra era la più corta tra quelle che coprivano t con quella posizione iniziale. Qualsiasi finestra che parte da lì e termina più avanti è più lunga, quindi tornare indietro non potrà mai trovare una risposta migliore.
In che modo Minimum Window Substring è diverso dal trovare un anagramma in una stringa?
Un anagramma contiene esattamente le lettere di t, quindi la sua finestra ha una lunghezza fissa m e scorre di un passo alla volta. Qui sono ammessi caratteri aggiuntivi, quindi la lunghezza fa parte della risposta: la finestra si allarga finché non copre t e si restringe finché continua a coprirlo.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def minWindow(s, t):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomenti
s = "mappingtheplan" t = "nap"
Output atteso
"plan"