Longest Substring Without Repeating Characters

+10

Du erhältst einen String s. Finde den längsten Teilstring, also eine Folge direkt aufeinanderfolgender Zeichen, in der kein Zeichen zweimal vorkommt, und gib seine Länge zurück.

Groß- und Kleinbuchstaben zählen als unterschiedliche Zeichen, daher ist a keine Wiederholung von A.

Funktion

lengthOfLongestSubstring(s: string) → integer

sstring: die zu durchsuchende Zeichenfolge
Gibt zurückinteger: die Länge der längsten Teilzeichenfolge ohne wiederholte Zeichen

Einschränkungen

1 ≤ s.length ≤ 5 × 10⁴
s enthält nur englische Buchstaben (Klein- und Großbuchstaben) und Ziffern.
Groß- und Kleinbuchstaben sind unterschiedliche Zeichen.

Beispiele

Eingabe: s = "coddycode"
Ausgabe: 5
Erklärung: ycode enthält fünf verschiedene Zeichen. Fügt man das d davor hinzu, ergibt sich dycode mit zweimal d, und keine andere Folge von fünf oder mehr Zeichen kommt ohne Wiederholung aus.

Eingabe: s = "racecar"
Ausgabe: 4
Erklärung: Sowohl race als auch ecar haben vier verschiedene Buchstaben. In jeder Folge von fünf Buchstaben kommt derselbe Buchstabe zweimal vor.

Eingabe: s = "a1b2a3b"
Ausgabe: 5
Erklärung: Ziffern zählen ebenfalls als Zeichen, daher hat 1b2a3 fünf verschiedene Zeichen. Beide Folgen aus sechs enthalten ein zweites a oder ein zweites b.

Weiterführende Frage

Was würdest du ändern, wenn s jedes Unicode-Zeichen statt Buchstaben und Ziffern enthalten könnte?

Lösung

Behalte ein Fenster: zwei Grenzen um einen Abschnitt ohne wiederholte Zeichen. Die rechte Grenze liest jedes Zeichen einmal, und die linke bewegt sich nur vorwärts. So findet ein Durchlauf für jedes Ende den längsten Abschnitt ohne Wiederholungen, der dort endet.

Jede Teilzeichenfolge überprüfen

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Probiere jeden Start- und Endpunkt aus und teste jeden Teilstring, indem du seine Zeichen zu einer Menge hinzufügst, bis eines davon bereits darin enthalten ist. Jeder Kandidat wird getestet, sodass der längste gültige nicht übersehen werden kann.

Es gibt etwa n²/2 Teilstrings, 1.25 × 10^9 für n = 5 × 10^4, und ein Test kann bis zu n Zeichen lesen: O(n³). Hier bricht ein Test nach höchstens 63 Zeichen ab, da der String nur 62 verschiedene Zeichen enthält, aber es bleiben trotzdem über eine Milliarde Tests.

Algorithmus

Setze best auf 0.
Durchlaufe für jeden Startindex jeden Endindex vom Start bis zum Ende der Zeichenfolge.
Füge die Zeichen des Teilstrings nacheinander zu einer leeren Menge hinzu und brich beim ersten Zeichen ab, das bereits in der Menge enthalten ist.
Wenn sich kein Zeichen wiederholt und der Teilstring best übertrifft, speichere seine Länge.
Gib best zurück.

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

Gleitfenster mit einer Menge

Idee

Wenn abc keine Wiederholung enthält, ist für die Prüfung von abcd nur eine Frage nötig: Ist d unter a, b und c? Eine Menge der Zeichen im Fenster beantwortet diese Frage sofort.

Bewege right Schritt für Schritt weiter. Wenn das neue Zeichen in der Menge enthalten ist, entferne von links Zeichen, bis seine vorherige Kopie entfernt ist. Füge es dann hinzu und miss die Länge. Du entfernst Zeichen nur, wenn es nötig ist. Daher ist das Fenster für jedes right die längste Folge ohne Wiederholungen, die dort endet, und die beste Teilzeichenfolge endet irgendwo. Jedes Zeichen kommt einmal in die Menge und verlässt sie höchstens einmal: O(n).

Algorithmus

Beginne mit einer leeren Menge, left = 0 und best = 0.
Gehe mit right über jeden Index.
Solange s[right] in der Menge ist, entferne s[left] und rücke left um einen Schritt vor.
Füge s[right] zur Menge hinzu.
Wenn right - left + 1 größer als best ist, speichere den Wert.
Gib best zurück.

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

Gleitendes Fenster, das zum Index des letzten Auftretens springt

Idee

Du weißt bereits, wo left landen muss: eine Position hinter der früheren Kopie des neuen Zeichens. Speichere den letzten Index jedes Zeichens in einer Map oder einem Array mit einem Eintrag pro Zeichencode, und left springt in einem Schritt dorthin.

Springe nur, wenn dieser Index bei left oder dahinter liegt. Eine ältere Kopie liegt bereits außerhalb des Fensters, und ein Sprung dorthin würde left rückwärts bewegen. Das Fenster ist bei jedem Schritt dasselbe, das die Set-Version aufbaut, und jedes Zeichen kostet jetzt einen Lookup, einen Vergleich und einen Schreibvorgang.

Algorithmus

Erstelle eine leere Map von Zeichen zu ihrem letzten Index und setze left = 0 und best = 0.
Gehe mit right jeden Index durch und lies das Zeichen ch an dieser Stelle.
Falls ch zuletzt an oder nach left gesehen wurde, setze left auf diesen Index plus eins.
Speichere right als letzten Index von ch.
Falls right - left + 1 größer als best ist, speichere diesen Wert.
Gib best zurück.

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

Stolperfallen und Grenzfälle

left nach hinten verschieben. In abba liegt das frühere a am Index 0 bereits außerhalb des Fensters, wenn du das letzte a erreichst. Wenn du zu Index 1 springst, kommt das zweite b wieder ins Fenster und das Ergebnis ist 3 statt 2.
Das Fenster als right - left zählen. Beide Enden liegen innerhalb des Fensters, also musst du eins addieren.
Den String zuerst in Kleinbuchstaben umwandeln. a und A sind hier unterschiedliche Zeichen, daher hat aA die Länge 2.
Nur messen, wenn ein Zeichen erneut auftritt. Bei einem String ohne Wiederholung, wie z, wird das nie ausgelöst, und die Antwort ist 0.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität der längsten Teilzeichenfolge ohne sich wiederholende Zeichen?

Das Sliding-Window-Verfahren läuft in O(n) Zeit, wobei n die Länge der Zeichenkette ist: Der rechte Rand liest jedes Zeichen einmal, und der linke Rand bewegt sich nur vorwärts. Der zusätzliche Speicherbedarf beträgt O(k), wobei k die Anzahl der verschiedenen Zeichen ist, die die Zeichenkette enthalten kann – hier 62.

Solltest du für die letzten Indizes eine Hash-Map oder ein Array verwenden?

Beide benötigen O(n) Zeit. Bei einer kleinen, festen Zeichenmenge wie hier vermeidet ein nach Zeichencode indiziertes Array das Hashing und ist schneller.

Was ist der Unterschied zwischen einem Teilstring und einer Teilsequenz?

Ein Teilstring ist ein Block aus Zeichen, die direkt nebeneinanderstehen, wie ode in coddycode. Eine Teilfolge kann Zeichen überspringen, wie cdy. Bei diesem Problem geht es um einen Teilstring, weshalb ein Fenster mit zwei Rändern funktioniert.

def lengthOfLongestSubstring(s):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

s = "coddycode"

Erwartete Ausgabe

Longest Substring Without Repeating Characters

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Jede Teilzeichenfolge überprüfen

Gleitfenster mit einer Menge

Gleitendes Fenster, das zum Index des letzten Auftretens springt

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben