HOWTO · Python
Längster Teilstring ohne sich wiederholende Zeichen in Python
Dieses Tutorial zeigt, wie Sie die längste Teilzeichenfolge erstellen, ohne Zeichen in Python zu wiederholen.
Auf dieser Seite
Die längste Teilzeichenfolge ohne wiederholte Zeichen ist der längste zusammenhängende Abschnitt einer Zeichenfolge, in dem jedes Zeichen genau einmal vorkommt. Eine Teilsequenz darf Zeichen überspringen, eine Teilzeichenfolge nicht. Die folgende Lösung gibt sowohl die Teilzeichenfolge als auch ihre Länge zurück, sodass Sie das Ergebnis verwenden können, das Ihr Programm benötigt.
Die längste Teilzeichenfolge ohne wiederholte Zeichen bestimmen
Ein gleitendes Fenster ist ein zusammenhängender Bereich, der durch eine linke Grenze und die aktuelle Zeichenposition beschrieben wird. Speichern Sie für jedes Zeichen seinen zuletzt gesehenen Index in einem Dictionary. Taucht ein Zeichen erneut innerhalb des aktuellen Fensters auf, verschieben Sie die linke Grenze direkt hinter seinen vorherigen Index. Liegt dieser Index bereits vor dem Fenster, lassen Sie die Grenze unverändert. Diese Invariante stellt sicher, dass jedes Zeichen im aktiven Fenster nur einmal vorkommt.
Führen Sie dieses Beispiel aus:
Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.
def longest_unique_substring(text):
last_seen = {}
left = 0
best_start = 0
best_length = 0
for right, char in enumerate(text):
previous = last_seen.get(char)
if previous is not None and previous >= left:
left = previous + 1
last_seen[char] = right
window_length = right - left + 1
if window_length > best_length:
best_start = left
best_length = window_length
return text[best_start:best_start + best_length], best_length
print(longest_unique_substring("ABCDEFGABCGHIJKLMNO"))
Mit dem Dictionary last_seen kann der Algorithmus die linke Grenze direkt verschieben, statt Zeichen einzeln zu entfernen. Wird der beste Startpunkt samt Länge nur aktualisiert, wenn ein längeres Fenster gefunden wird, bleibt außerdem das erste Ergebnis erhalten, falls mehrere Teilzeichenfolgen gleich lang sind.
Eine while-Schleife mit einem gleitenden Fenster verwenden
Mit einer while-Schleife lässt sich dieselbe Fensterbewegung über einen expliziten rechten Index ausdrücken. Die Funktion gibt dasselbe Wertepaar wie die erste Implementierung zurück: zuerst die Teilzeichenfolge, dann ihre Länge. Bei einer leeren Eingabe wird die Schleife nicht ausgeführt; das zurückgegebene Paar besteht dann aus einer leeren Zeichenfolge und 0.
Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.
def longest_unique_substring_while(text):
last_seen = {}
left = 0
right = 0
best_start = 0
best_length = 0
while right < len(text):
char = text[right]
previous = last_seen.get(char)
if previous is not None and previous >= left:
left = previous + 1
last_seen[char] = right
window_length = right - left + 1
if window_length > best_length:
best_start = left
best_length = window_length
right += 1
return text[best_start:best_start + best_length], best_length
Eine for-Schleife mit einem gleitenden Fenster verwenden
Die obige for-Variante bewegt right mithilfe von enumerate weiter. Jeder Durchlauf verarbeitet ein Zeichen und aktualisiert denselben Zustand. So sind die Indexfortschaltung und die Fensterlogik voneinander getrennt, und der manuelle Schritt des while-Durchlaufs entfällt. Beide Varianten verwenden dieselbe Invariante und liefern dasselbe Ergebnis. Wählen Sie daher die Schleifenform, die in Ihrer Codebasis klarer ist.
Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.
def longest_unique_substring_for(text):
last_seen = {}
left = 0
best_start = 0
best_length = 0
for right, char in enumerate(text):
previous = last_seen.get(char)
if previous is not None and previous >= left:
left = previous + 1
last_seen[char] = right
window_length = right - left + 1
if window_length > best_length:
best_start = left
best_length = window_length
return text[best_start:best_start + best_length], best_length
Das Beispiel nachvollziehen und Randfälle prüfen
Bei ABCDEFGABCGHIJKLMNO bilden die ersten sieben Zeichen ein eindeutiges Fenster. Das nächste A an Index 7 wiederholt das Zeichen an Index 0; deshalb verschiebt sich die linke Grenze auf Index 1. Die folgenden Wiederholungen von B und C verschieben sie auf die Indizes 2 und 3. Wenn das zweite G an Index 10 erscheint, liegt das erste G an Index 6 und damit innerhalb des aktuellen Fensters, das bei Index 3 beginnt. Die Wiederholung verschiebt die linke Grenze deshalb von Index 3 auf Index 7, und das Fenster wächst bis zum Ende der Eingabe. Die längste Teilzeichenfolge ist ABCGHIJKLMNO und hat die Länge 12.
Bei einer leeren Eingabe lautet das Ergebnis ("", 0). Wenn jedes Zeichen nur einmal vorkommt, ist die gesamte Eingabe das Ergebnis. Eine Wiederholung innerhalb des aktuellen Fensters verschiebt dessen linke Grenze; eine Wiederholung vor dem Fenster tut das nicht. Mit diesen Fällen lässt sich prüfen, ob der Algorithmus ein neu auftretendes doppeltes Zeichen korrekt behandelt; eine Wiederholung, deren vorheriger Index bereits vor dem Fenster liegt, lässt die Grenze unverändert, wie die Invariante oben besagt.
Zeit- und Speicherkomplexität analysieren
Der Algorithmus besucht jedes Zeichen einmal. Jeder Dictionary-Zugriff und jede Aktualisierung benötigt im Durchschnitt konstante Zeit. Für eine Zeichenfolge der Länge n beträgt die erwartete Laufzeit daher O(n). Das Dictionary speichert den zuletzt gesehenen Index jedes unterschiedlichen Zeichens und benötigt O(min(n, k)) Speicherplatz. Dabei ist k die Anzahl der möglichen unterschiedlichen Zeichen im Zeichensatz der Eingabe. Die zurückgegebene Teilzeichenfolge benötigt in Python Speicher proportional zu ihrer Länge, weil beim Slicing eine neue Zeichenfolge entsteht.
