Longest Substring Without Repeating Characters

+10

Ricevi una stringa s. Trova la sottostringa più lunga, una sequenza di caratteri adiacenti, in cui nessun carattere compare due volte, e restituiscine la lunghezza.

Le lettere maiuscole e minuscole sono considerate caratteri diversi, quindi a e A non sono ripetizioni.

Funzione

lengthOfLongestSubstring(s: string) → integer

sstring: la stringa da cercare
Restituisceinteger: la lunghezza della sottostringa più lunga senza caratteri ripetuti

Vincoli

1 ≤ s.length ≤ 5 × 10⁴
s contiene solo lettere inglesi (minuscole e maiuscole) e cifre.
Le lettere maiuscole e minuscole sono caratteri diversi.

Esempi

Input: s = "coddycode"
Output: 5
Spiegazione: ycode contiene cinque caratteri diversi. Aggiungendo d prima di esso si ottiene dycode, con d due volte, e nessun'altra sequenza di cinque o più caratteri evita una ripetizione.

Input: s = "racecar"
Output: 4
Spiegazione: Sia race sia ecar hanno quattro lettere diverse. Ogni sequenza di cinque lettere contiene due volte la stessa lettera.

Input: s = "a1b2a3b"
Output: 5
Spiegazione: Anche le cifre contano come caratteri, quindi 1b2a3 ne contiene cinque diversi. Entrambe le sequenze di sei contengono una seconda a o una seconda b.

Per approfondire

Che cosa cambieresti se s potesse contenere qualsiasi carattere Unicode invece di lettere e cifre?

Soluzione

Mantieni una finestra: due estremi intorno a una sequenza senza caratteri ripetuti. L’estremo destro legge ogni carattere una sola volta e quello sinistro si sposta solo in avanti, quindi una sola scansione trova, per ogni estremo, la sequenza più lunga senza ripetizioni che termina lì.

Controlla ogni sottostringa

Corretto, ma non termina sui test più grandi

Intuizione

Prova ogni inizio e fine e verifica ogni sottostringa aggiungendo i suoi caratteri a un insieme finché uno non è già presente. Ogni candidata viene verificata, quindi non si può non individuare quella valida più lunga.

Ci sono circa n²/2 sottostringhe, 1.25 × 10^9 per n = 5 × 10^4, e una verifica può leggere fino a n caratteri: O(n³). Qui una verifica si ferma dopo al massimo 63 caratteri, dato che la stringa contiene solo 62 caratteri diversi, ma restano comunque oltre un miliardo di verifiche.

Algoritmo

Imposta best a 0.
Per ogni indice iniziale, esegui un ciclo su ogni indice finale, dall'inizio alla fine della stringa.
Aggiungi i caratteri della sottostringa uno alla volta a un insieme vuoto e fermati al primo carattere già presente nell'insieme.
Se nessun carattere si ripete e la sottostringa supera best, memorizzane la lunghezza.
Restituisci best.

def lengthOfLongestSubstring(s):
    def has_no_repeat(start, end):
        seen = set()
        for k in range(start, end + 1):
            if s[k] in seen:
                return False
            seen.add(s[k])
        return True

    best = 0
    n = len(s)
    for start in range(n):
        for end in range(start, n):
            if has_no_repeat(start, end):
                best = max(best, end - start + 1)
    return best

Finestra scorrevole con un insieme

Intuizione

Se abc non contiene ripetizioni, verificare abcd richiede una sola domanda: d è tra a, b e c? Un insieme dei caratteri della finestra risponde subito.

Sposta right di un passo alla volta. Se il nuovo carattere è nell’insieme, rimuovi i caratteri da sinistra finché la sua copia precedente non è stata eliminata, poi aggiungilo e misura. Elimini caratteri solo quando è necessario, quindi per ogni right la finestra è la sequenza più lunga senza ripetizioni che termina lì, e la sottostringa migliore termina da qualche parte. Ogni carattere entra nell’insieme una volta ed esce al massimo una volta: O(n).

Algoritmo

Inizia con un insieme vuoto, left = 0 e best = 0.
Sposta right su ogni indice.
Mentre s[right] è nell’insieme, rimuovi s[left] e sposta left avanti di un passo.
Aggiungi s[right] all’insieme.
Se right - left + 1 supera best, memorizzalo.
Restituisci best.

def lengthOfLongestSubstring(s):
    in_window = set()  # the characters between left and right
    left = 0
    best = 0
    for right in range(len(s)):
        # Shrink from the left until s[right] is no longer inside.
        while s[right] in in_window:
            in_window.remove(s[left])
            left += 1
        in_window.add(s[right])
        best = max(best, right - left + 1)
    return best

Finestra scorrevole che salta all’indice dell’ultima occorrenza

Intuizione

Sai già dove deve arrivare left: subito dopo la copia precedente del nuovo carattere. Memorizza l’ultimo indice di ogni carattere in una mappa o in un array con una posizione per ogni codice carattere, e left ci salta in un solo passaggio.

Salta solo quando quell’indice è maggiore o uguale a left. Una copia precedente è già fuori dalla finestra e saltarci sposterebbe left all’indietro. La finestra a ogni passaggio è quella che costruisce la versione con l’insieme, e ora ogni carattere richiede una ricerca, un confronto e una scrittura.

Algoritmo

Crea una mappa vuota dai caratteri all'ultimo indice e imposta left = 0 e best = 0.
Sposta right su ogni indice, leggendo il carattere ch in quella posizione.
Se ch è stato visto l'ultima volta all'indice left o successivamente, imposta left su quell'indice più uno.
Registra right come ultimo indice di ch.
Se right - left + 1 è maggiore di best, memorizzalo.
Restituisci best.

def lengthOfLongestSubstring(s):
    last_seen = {}
    start = 0
    best = 0
    for i, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= start:
            start = last_seen[ch] + 1
        last_seen[ch] = i
        if i - start + 1 > best:
            best = i - start + 1
    return best

Trappole e casi limite

Spostare left all'indietro. In abba, la a precedente all'indice 0 è già fuori dalla finestra quando raggiungi l'ultima a. Saltando all'indice 1, la seconda b rientra e si ottiene 3 invece di 2.
Contare la finestra come right - left. Entrambi gli estremi sono al suo interno, quindi aggiungi uno.
Convertire prima la stringa in minuscolo. Qui a e A sono caratteri diversi, quindi aA ha lunghezza 2.
Misurare solo quando compare una ripetizione. Una stringa senza ripetizioni, come z, non la attiva mai e il risultato è 0.

Domande frequenti3

Qual è la complessità temporale di «Longest Substring Without Repeating Characters»?

La finestra scorrevole richiede un tempo O(n), dove n è la lunghezza della stringa: il bordo destro legge ogni carattere una volta e il bordo sinistro si sposta solo in avanti. Lo spazio aggiuntivo è O(k), dove k è il numero di caratteri diversi che la stringa può contenere, 62 in questo caso.

Dovresti usare una tabella hash o un array per gli ultimi indici?

Entrambi richiedono un tempo O(n). Con un insieme fisso e piccolo di caratteri, come in questo caso, un array indicizzato tramite il codice del carattere evita l'hashing ed è più veloce.

Qual è la differenza tra una sottostringa e una sottosequenza?

Una sottostringa è un blocco di caratteri che si trovano uno accanto all'altro, come ode in coddycode. Una sottosequenza può saltare dei caratteri, come cdy. Questo problema richiede una sottostringa, ed è per questo che funziona una finestra con due estremi.

def lengthOfLongestSubstring(s):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

s = "coddycode"

Output atteso

Longest Substring Without Repeating Characters

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Controlla ogni sottostringa

Finestra scorrevole con un insieme

Finestra scorrevole che salta all’indice dell’ultima occorrenza

Trappole e casi limite

Domande frequenti3

Problemi simili