Sottostringa più lunga senza ripetizioni
Tenere traccia delle ultime posizioni viste in una finestra
Sottostringa più lunga senza ripetizioni è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 3 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.
Un classico problema sulle finestre
Trovi la sottostringa più lunga senza caratteri ripetuti. È un classico delle finestre scorrevoli, presente in quasi tutte le piattaforme di valutazione. 🔤
La trappola della forza bruta
Controllare ogni sottostringa alla ricerca di duplicati costa circa O(n^2) o anche di più. Per stringhe lunghe è decisamente troppo lento, quindi serve una scansione più intelligente.
Una finestra di caratteri distinti
Mantenga una finestra che contenga sempre caratteri distinti. La espanda verso destra e, quando compare una ripetizione, la restringa da sinistra finché la ripetizione non scompare.
Ricordare le ultime posizioni
Memorizzi l'ultimo indice di ogni carattere in un dizionario. In questo modo, durante la scansione, saprà immediatamente dove è stata vista l'ultima ripetizione.
last = {}
left = 0
best = 0Scansionare ogni carattere
Esegua un ciclo usando right sulla stringa, leggendo sia l'indice sia il carattere a ogni passaggio. Questo fa avanzare la finestra di una posizione alla volta.
for right, ch in enumerate(s):Spostare rapidamente il puntatore left
Se il carattere è stato visto all'interno della finestra corrente, sposti left subito dopo la sua ultima posizione. In questo modo rimuove il duplicato con un solo spostamento.
if ch in last and last[ch] >= left:
left = last[ch] + 1Aggiornare e misurare
Memorizzi la nuova posizione del carattere; a quel punto la finestra da left a right non contiene duplicati. La sua lunghezza è right meno left più uno.
last[ch] = right
best = max(best, right - left + 1)Perché il controllo è importante
Il controllo last[ch] >= left è essenziale. Senza di esso, una vecchia posizione esterna alla finestra farebbe erroneamente arretrare left.
Tempo e spazio lineari
Ogni carattere viene visitato una volta e left si muove solo in avanti, quindi la scansione è O(n). Il dizionario usa spazio per i caratteri distinti.
Casi limite da gestire
Una stringa vuota produce zero, mentre una stringa composta da una sola lettera ripetuta produce uno. Verifichi entrambi i casi prima dell'invio, per evitare un WA insidioso.
Lo schema riutilizzabile
La mappa delle ultime occorrenze e il puntatore left che salta in avanti si generalizzano a molti problemi di distinzione, come le finestre con al massimo una ripetizione.
Verifica rapida
Memorizzi l'ultimo indice di ogni carattere mentre cerca la sottostringa senza ripetizioni più lunga.
Riepilogo
Faccia scorrere una finestra di caratteri distinti, memorizzi ogni ultima posizione e sposti left oltre le ripetizioni. Questo risolve il problema classico in O(n). ✅
Domande Frequenti
La lezione «Sottostringa più lunga senza ripetizioni» è gratuita?
Sì — il testo completo di «Sottostringa più lunga senza ripetizioni» è 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 «Sottostringa più lunga senza ripetizioni»?
Tenere traccia delle ultime posizioni viste in una finestra 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 3 di 4.
Quanto tempo richiede la lezione «Sottostringa più lunga senza ripetizioni»?
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
- Somme su finestre di dimensione fissa
- Finestra variabile con due puntatori
- Sottostringa più lunga senza ripetizioni
- Contare le finestre che soddisfano una regola