Längster Teilstring ohne Wiederholungen
Verfolgen Sie die zuletzt gesehenen Positionen in einem Fenster
Längster Teilstring ohne Wiederholungen ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Ein klassisches Fensterproblem
Finden Sie die längste Teilzeichenkette ohne wiederholte Zeichen. Dieses beliebte Problem zum gleitenden Fenster taucht bei fast jedem Online Judge auf. 🔤
Die Falle der vollständigen Suche
Jede Teilzeichenkette auf Duplikate zu prüfen, kostet etwa O(n^2) oder mehr. Bei langen Zeichenketten ist das viel zu langsam, daher benötigen Sie einen intelligenteren Durchlauf.
Ein Fenster eindeutiger Zeichen
Halten Sie ein Fenster, das stets verschiedene Zeichen enthält. Erweitern Sie es nach rechts. Sobald ein Zeichen wiederholt vorkommt, verkleinern Sie das Fenster von links, bis die Wiederholung verschwunden ist.
Die letzten Positionen speichern
Speichern Sie den letzten Index jedes Zeichens in einem Dictionary. So erkennen Sie beim Durchlauf sofort, an welcher Position die letzte Wiederholung auftrat.
last = {}
left = 0
best = 0Jedes Zeichen durchlaufen
Durchlaufen Sie die Zeichenkette mit right und lesen Sie bei jedem Schritt sowohl den Index als auch das Zeichen an dieser Position. Dadurch bewegt sich das Fenster Schritt für Schritt vorwärts.
for right, ch in enumerate(s):Den linken Zeiger springen lassen
Wenn das Zeichen innerhalb des aktuellen Fensters vorkam, verschieben Sie left direkt hinter seine letzte Position. Damit entfernen Sie das Duplikat in einem Schritt.
if ch in last and last[ch] >= left:
left = last[ch] + 1Aktualisieren und messen
Speichern Sie die neue Position dieses Zeichens. Danach ist das Fenster von left bis right frei von Duplikaten. Seine Länge beträgt right minus left plus eins.
last[ch] = right
best = max(best, right - left + 1)Warum die Prüfung wichtig ist
Die Prüfung last[ch] >= left ist unverzichtbar. Ohne sie würde eine alte Position außerhalb des Fensters left fälschlicherweise nach hinten verschieben.
Lineare Zeit, linearer Speicher
Jedes Zeichen wird einmal besucht und left bewegt sich nur vorwärts, daher läuft der Durchlauf in O(n). Das Dictionary benötigt Speicherplatz für die verschiedenen Zeichen.
Diese Randfälle abdecken
Eine leere Zeichenkette ergibt null, und eine Zeichenkette aus nur einem wiederholten Buchstaben ergibt eins. Überprüfen Sie beides vor der Abgabe, um ein tückisches WA zu vermeiden.
Das wiederverwendbare Muster
Die Map der zuletzt gesehenen Positionen zusammen mit einem springenden linken Zeiger lässt sich auf viele Probleme mit verschiedenen Zeichen verallgemeinern, etwa auf Fenster mit höchstens einer Wiederholung.
Kurzer Check
Sie speichern beim Durchlauf auf der Suche nach der längsten Teilzeichenkette ohne Wiederholungen den letzten Index jedes Zeichens.
Zusammenfassung
Verschieben Sie ein Fenster eindeutiger Zeichen, speichern Sie für jedes Zeichen die letzte Position und springen Sie bei Wiederholungen mit left darüber hinweg. Damit lösen Sie das klassische Problem in O(n). ✅
Häufig gestellte Fragen
Ist die Lektion „Längster Teilstring ohne Wiederholungen“ kostenlos?
Ja — der vollständige Text von „Längster Teilstring ohne Wiederholungen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Längster Teilstring ohne Wiederholungen“?
Verfolgen Sie die zuletzt gesehenen Positionen in einem Fenster Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Längster Teilstring ohne Wiederholungen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Summen in Fenstern fester Größe
- Variables Fenster mit zwei Zeigern
- Längster Teilstring ohne Wiederholungen
- Fenster zählen, die eine Regel erfüllen