Minimum Window Substring

Q: Che cosa conta il contatore mancante?

È il numero di copie dei caratteri richieste da t che la finestra non contiene ancora, ovvero la somma dei valori positivi in need . Inizia con la lunghezza di t ed è esattamente 0 quando la finestra contiene t . Le copie in eccesso non lo modificano: è questo che permette a un solo confronto di sostituire una scansione di ogni lettera.

Q: In che modo Minimum Window Substring è diverso dal trovare un anagramma in una stringa?

Un anagramma contiene esattamente le lettere di t e nessun'altra, quindi la finestra ha una lunghezza fissa di m e scorre di un passo alla volta. In questo caso, la finestra può contenere caratteri aggiuntivi, quindi la sua lunghezza fa parte della risposta: cresce a destra finché non contiene t e si restringe a sinistra finché continua a contenerlo.

DifficileFinestra scorrevole Hashing

+10

Ti vengono date due stringhe, s e t. Trova la sottostringa più corta di s, ovvero una sequenza di caratteri consecutivi, che contenga ogni carattere di t, contando anche le ripetizioni: se t contiene due volte una lettera, la sottostringa deve contenerla almeno due volte. L’ordine non è importante e la sottostringa può contenere anche altri caratteri.

Se più sottostringhe hanno la stessa lunghezza minima, restituisci quella più a sinistra. Se nessuna sottostringa di s contiene tutti i caratteri di t, restituisci una stringa vuota.

Funzione

minWindow(s: string, t: string) → string

sstring: la stringa in cui cercare
tstring: i caratteri che la finestra deve contenere, comprese le ripetizioni
Restituiscestring: la sottostringa più corta e, a parità di lunghezza, quella più a sinistra di s che contiene tutti i caratteri di t, oppure una stringa vuota

Vincoli

1 ≤ s.length ≤ 5 × 10⁴
1 ≤ t.length ≤ 10⁴
s e t contengono solo lettere inglesi. Le lettere maiuscole e minuscole sono caratteri diversi.
Quando diverse sottostringhe hanno la lunghezza minima, la risposta è quella più a sinistra; se non ne esiste nessuna, è "".

Esempi

Input: s = "mappingtheplan"t = "nap"
Output: "plan"
Spiegazione: Leggendo da sinistra, la prima finestra che contiene una n, una a e una p è appin, lunga cinque caratteri. plan alla fine le contiene tutte e tre in quattro caratteri, e nessuna sequenza di tre caratteri le contiene.

Input: s = "banana"t = "aan"
Output: "ana"
Spiegazione: t richiede due copie di a e una n. ana all’indice 1 contiene esattamente queste lettere. Una seconda ana inizia all’indice 3 e vince quella più a sinistra.

Input: s = "Coddy"t = "cd"
Output: ""
Spiegazione: L'unica C in Coddy è maiuscola, e le lettere maiuscole e minuscole sono caratteri diversi. Nessuna sottostringa contiene una c minuscola, quindi la risposta è la stringa vuota.

+17 test nascosti all’invio

Per approfondire

Quando t usa solo poche lettere e s è lunga, gran parte di s non può mai essere rilevante. 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ù.

0 di 3 aperti

Soluzione

La risposta dipende da quanti caratteri di ogni tipo contiene una finestra, non dal loro ordine, e la finestra migliore può iniziare ovunque. Provare ogni inizio con ogni fine significa avere O(n²) finestre. La soluzione è una finestra i cui bordi si spostano solo in avanti: il bordo destro la allarga finché non contiene t, quello sinistro la restringe finché continua a contenerlo e un contatore dei caratteri mancanti ti dice in un solo passaggio se contiene t.

Fai crescere una finestra da ogni punto di partenza

Corretto, ma non termina sui test più grandi

Intuizione

Fissa il punto in cui inizia la sottostringa. Poi estendila di un carattere alla volta, tenendo il conto di ogni carattere al suo interno e, dopo ogni passaggio, controlla se copre t: per ciascuna delle u lettere diverse usate da t, la finestra deve contenere almeno tante copie quante ne contiene t. Il primo estremo che soddisfa questa condizione determina la finestra minima che copre la sottostringa per questo punto di partenza, perché tutte le finestre più corte con lo stesso punto di partenza sono state controllate prima e non hanno soddisfatto la condizione. Fermati lì.

Ripeti l’operazione per ogni punto di partenza e conserva la finestra più corta. I punti di partenza vengono provati da sinistra a destra e una finestra sostituisce la migliore solo se è strettamente più corta, quindi tra finestre di uguale lunghezza rimane quella più a sinistra.

È lento quando le finestre sono lunghe o non esistono. Se l’unica Z in s si trova proprio alla fine e t ne richiede una, ogni punto di partenza legge fino alla fine: circa n²/2 passaggi, ovvero 1.25 × 10^9 per n = 5 × 10^4, ognuno con un controllo su un massimo di 52 lettere. Lo stesso accade quando non esiste alcuna finestra.

Algoritmo

Conta quante copie di ogni carattere t richiede e fai un elenco delle lettere che usa.
Per ogni start, azzera una tabella dei conteggi e sposta end da start fino alla fine di s, aggiungendo s[end] alla tabella.
Dopo ogni aggiunta, controlla ogni lettera di t. Se la finestra ne contiene un numero sufficiente per ciascuna, confronta la sua lunghezza con la migliore finora, conservala se è strettamente più corta e smetti di estendere la finestra.
Dopo aver esaminato tutti i punti di partenza, restituisci la finestra migliore oppure "" se nessuna conteneva tutte le lettere di t.

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

Due fatti eliminano la necessità di ricominciare. Aggiungere caratteri a una finestra che copre t fa sì che continui a coprirlo, e rimuovere caratteri da una finestra a cui manca qualcosa fa sì che continui a mancarle. Quindi, quando l’inizio si sposta a destra, la fine della finestra più corta che copre t può solo restare dov’è o spostarsi a destra. Entrambi i margini possono avanzare insieme e nessuno dei due torna mai indietro.

Sposta right lungo s, aggiungendo ogni carattere a una tabella di conteggi. Ogni volta che la finestra copre t, è una candidata: registrala se è più corta della migliore, quindi rimuovi s[left] e sposta left in avanti, poi controlla di nuovo. Ripeti finché la finestra smette di coprire t, quindi torna ad allargarla verso destra.

Non viene tralasciuna alcuna finestra. Considera la finestra migliore, da L a R. Se left avesse superato L prima che right raggiungesse R, una finestra da L con fine prima di R avrebbe coperto t e sarebbe stata più corta della migliore. Quindi, quando right raggiunge R, il ciclo di restringimento fa avanzare left fino a L e registra la finestra migliore. Ogni margine si sposta al massimo n volte, ma a ogni controllo vengono letti fino a u conteggi, uno per ogni lettera usata da t, anche se dall’ultimo controllo è cambiato un solo conteggio.

Algoritmo

Conta le copie richieste da t ed elenca le sue lettere; inizia con una finestra vuota, left = 0 e una lunghezza migliore pari a n+1.
Sposta right su ogni indice e aggiungi s[right] ai conteggi della finestra.
Finché ogni lettera di t è presente nella finestra in quantità sufficiente, registra la finestra se è strettamente più corta della migliore, rimuovi s[left] dai conteggi e sposta left in avanti.
Restituisci la finestra migliore oppure "" se la lunghezza migliore è ancora n+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 dei mancanti

Intuizione

Mantieni la stessa finestra e sostituisci il controllo con un numero. Sia need[c] il numero di copie di c richieste da t meno le copie presenti nella finestra. Un valore positivo significa che alla finestra ne mancano ancora alcune, mentre un valore negativo significa che ne ha in eccesso. Sia missing il numero totale di copie che mancano alla finestra, inizialmente pari alla lunghezza di t. La finestra contiene esattamente t quando missing è 0.

Aggiornarlo costa un solo passaggio. Quando s[right] entra e il valore di need per quel carattere è maggiore di 0, colma una lacuna, quindi missing diminuisce di uno; in ogni caso, need diminuisce di uno e può scendere sotto 0, indicando un eccesso. Quando s[left] esce, need aumenta di uno e, se ora è maggiore di 0, significa che la finestra ha ceduto una copia necessaria a t, quindi missing aumenta di uno. Le copie in eccesso entrano ed escono senza modificare missing.

Seguiamo s = banana, t = aan: inizialmente need vale 2 per a e 1 per n, mentre missing vale 3. b non serve. La prima a porta missing a 2, la n a 1, la seconda a a 0, quindi bana contiene t. Riducendo la finestra, si elimina la b in eccesso e rimane ana, di tre caratteri, che diventa la migliore. Eliminando quella a, missing torna a 1. L'ultima a fa sì che la finestra contenga di nuovo t con nana, che si riduce alla seconda ana. Non è più corta, quindi rimane la prima ana.

Ogni carattere di s entra nella finestra una volta ed esce al massimo una volta, e ogni spostamento richiede una quantità fissa di lavoro. Per costruire need si legge t una volta. L'intera esecuzione richiede O(n + m), con una tabella di 128 conteggi come unica memoria aggiuntiva.

Algoritmo

Riempi need con le occorrenze di t e imposta missing alla lunghezza di t, left = 0 e la lunghezza migliore a n+1.
Per ogni right: se need[s[right]] è maggiore di 0, diminuisci missing; poi diminuisci need[s[right]].
Mentre missing è 0, registra la finestra se è strettamente più corta della migliore. Poi aumenta need[s[left]]; se ora è maggiore di 0, aumenta missing. Avanza left.
Restituisci la finestra migliore, oppure "" se la lunghezza migliore è ancora n+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

La maggior parte delle risposte sbagliate conta la cosa sbagliata o registra la finestra nel momento sbagliato.

Contare le lettere invece delle copie. t = aan richiede due a, quindi ban non lo copre.
Diminuire missing per ogni carattere che entra. Una terza a è in più; se diminuisce missing, il contatore raggiunge 0 mentre nella finestra manca ancora la n. Diminuirlo solo quando need era maggiore di 0.
Aumentare missing per ogni carattere che esce. Eliminare un carattere in più lascia la finestra in grado di coprire t; aumentarlo solo quando need supera 0.
Registrare la finestra dopo il ciclo di riduzione. A quel punto non copre più t. Registrala all'interno del ciclo, prima di rimuovere s[left].
Sostituire la finestra migliore quando la nuova ha la stessa lunghezza. In questo modo si restituisce la finestra più a destra tra quelle più corte; confronta usando un minore stretto.
Usare n come lunghezza per «non trovato». Quando la risposta è l'intera s, anche la sua lunghezza è n. Parti da n+1 in modo che i due casi siano distinti.
Una tabella di 26 posizioni indicizzata da c - 'a'. Le lettere maiuscole non rientrano nella tabella. Usa una posizione per ogni codice carattere.

Domande frequenti4

Qual è la complessità temporale di Minimum Window Substring?

La finestra scorrevole con un contatore dei caratteri mancanti richiede un tempo O(n + m), dove n e m sono le lunghezze di s e t. La creazione della tabella legge t una volta, e ogni carattere di s entra ed esce dalla finestra al massimo una volta, con un costo fisso per ogni spostamento. La memoria aggiuntiva consiste in una tabella con un conteggio per ogni codice carattere, che non aumenta con la dimensione dell'input.

Perché il bordo sinistro non si sposta mai indietro?

Il bordo sinistro supera una posizione solo dopo che una finestra che inizia lì ha coperto t, e quella era la finestra più corta che copriva t a partire da quella posizione. Qualsiasi finestra che inizia lì e termina più avanti è più lunga, quindi tornare indietro non potrebbe mai trovare una risposta migliore. Ecco perché entrambi i bordi avanzano una sola volta e il lavoro rimane lineare.

Che cosa conta il contatore mancante?

È il numero di copie dei caratteri richieste da t che la finestra non contiene ancora, ovvero la somma dei valori positivi in need. Inizia con la lunghezza di t ed è esattamente 0 quando la finestra contiene t. Le copie in eccesso non lo modificano: è questo che permette a un solo confronto di sostituire una scansione di ogni lettera.

In che modo Minimum Window Substring è diverso dal trovare un anagramma in una stringa?

Un anagramma contiene esattamente le lettere di t e nessun'altra, quindi la finestra ha una lunghezza fissa di m e scorre di un passo alla volta. In questo caso, la finestra può contenere caratteri aggiuntivi, quindi la sua lunghezza fa parte della risposta: cresce a destra finché non contiene t e si restringe a sinistra finché continua a contenerlo.

Python

def minWindow(s, t):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

s = "mappingtheplan"
t = "nap"

Atteso

"plan"

Minimum Window Substring

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Fai crescere una finestra da ogni punto di partenza

Finestra scorrevole che controlla ogni lettera

Finestra scorrevole con un contatore dei mancanti

Trappole e casi limite

Domande frequenti4

Problemi simili