Minimum Window Substring

Q: Wie hoch ist die Zeitkomplexität von „Minimum Window Substring“?

Das Fenster mit fehlendem Zähler läuft in O(n + m) Zeit, wobei n und m die Längen von s und t sind. Beim Erstellen der Tabelle wird t einmal durchlaufen, und jedes Zeichen von s tritt höchstens einmal in das Fenster ein und verlässt es höchstens einmal. Der zusätzliche Speicherbedarf beträgt einen Zähler pro Zeichencode.

Q: Worin unterscheidet sich Minimum Window Substring davon, ein Anagramm in einer Zeichenkette zu finden?

Ein Anagramm enthält genau die Buchstaben von t , daher hat sein Fenster eine feste Länge von m und verschiebt sich Schritt für Schritt. Hier sind zusätzliche Zeichen erlaubt, daher ist die Länge Teil der Antwort: Das Fenster wächst, bis es t abdeckt, und schrumpft, solange es das weiterhin tut.

SchwerSliding Window Hashing

+10

Du erhältst zwei Zeichenketten, s und t. Finde die kürzeste Teilzeichenkette von s, die jedes Zeichen von t enthält, wobei Wiederholungen mitgezählt werden: Wenn t einen Buchstaben zweimal enthält, muss die Teilzeichenkette ihn mindestens zweimal enthalten. Die Reihenfolge spielt keine Rolle, und es dürfen auch andere Zeichen vorkommen.

Wenn mehrere Teilzeichenketten am kürzesten sind, gib die am weitesten links stehende zurück. Wenn keine alle Zeichen von t enthält, gib eine leere Zeichenkette zurück.

Funktion

minWindow(s: string, t: string) → string

sstring: die Zeichenfolge, in der gesucht werden soll
tstring: die Zeichen, die das Fenster enthalten muss, einschließlich Wiederholungen
Gibt zurückstring: die kürzeste und dann am weitesten links stehende Teilzeichenfolge von s, die alle Zeichen von t enthält, oder eine leere Zeichenfolge

Einschränkungen

1 ≤ s.length ≤ 5 × 10⁴
1 ≤ t.length ≤ 10⁴
s und t enthalten ausschließlich englische Buchstaben. Groß- und Kleinbuchstaben sind unterschiedliche Zeichen.
Wenn mehrere Teilzeichenfolgen am kürzesten sind, ist die Antwort die am weitesten links stehende; wenn keine vorhanden ist, lautet sie "".

Beispiele

Eingabe: s = "mappingtheplan"t = "nap"
Ausgabe: "plan"
Erklärung: Das erste Fenster von links, das ein n, ein a und ein p enthält, ist appin und fünf Zeichen lang. plan enthält alle drei auf vier Zeichen verteilt, und kein Lauf aus drei Zeichen tut das.

Eingabe: s = "banana"t = "aan"
Ausgabe: "ana"
Erklärung: t verlangt zwei Kopien von a und ein n. ana an Index 1 enthält genau das. Ein zweites ana beginnt an Index 3, und das linkeste gewinnt.

Eingabe: s = "Coddy"t = "cd"
Ausgabe: ""
Erklärung: Das C in Coddy ist großgeschrieben und damit ein anderes Zeichen als c. Kein Teilstring enthält ein kleingeschriebenes c, daher ist die Antwort die leere Zeichenkette.

Weiterführende Frage

Wenn t wenige Buchstaben hat und s lang ist, ist der größte Teil von s nie relevant. Kannst du das Fenster nur zwischen Positionen verschieben, an denen ein Buchstabe aus t steht?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Es zählen nur die Häufigkeiten in einem Fenster, nicht ihre Reihenfolge. Verschiebe den rechten Rand, bis das Fenster t abdeckt, und dann den linken Rand, solange es das noch tut; keiner der beiden Ränder bewegt sich zurück. Ein Zähler für fehlende Zeichen zeigt dir mit einem einzigen Schritt, ob das Fenster t abdeckt.

Vergrößere ein Fenster von jedem Startpunkt aus

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

Idee

Fixiere einen Start und erweitere das Fenster Zeichen für Zeichen, wobei du die Anzahl jedes Zeichens mitzählt. Prüfe nach jedem Schritt jeden der u Buchstaben, die t enthält. Das erste Ende, das die Bedingung erfüllt, ergibt das kürzeste abdeckende Fenster ab diesem Start, also höre dort auf. Die Starts werden von links nach rechts durchlaufen und nur ein strikt kürzeres Fenster ersetzt das bisher beste, sodass bei Gleichstand das am weitesten links liegende erhalten bleibt.

Wenn kein Fenster existiert, wird bei jedem Start bis zum Ende von s gelesen: etwa n²/2 Schritte, 1.25 × 10^9 für n = 5 × 10^4.

Algorithmus

Zähle die Vorkommen jedes Buchstabens, die t verlangt.
Leere für jedes start eine Zähltabelle und bewege end nach rechts, wobei du s[end] hinzufügst.
Sobald das Fenster genügend Vorkommen jedes Buchstabens enthält, behalte es, wenn es strikt kürzer als das bisher beste ist, und gehe zum nächsten Start.
Gib das beste Fenster zurück oder "", falls keines t abgedeckt hat.

def minWindow(s, t):
    need = [0] * 128  # copies of each character code that t asks for
    for ch in t:
        need[ord(ch)] += 1
    letters = [c for c in range(128) if need[c] > 0]
    best_start, best_len = 0, len(s) + 1
    for start in range(len(s)):
        have = [0] * 128  # counts inside s[start..end]
        for end in range(start, len(s)):
            have[ord(s[end])] += 1
            if all(have[c] >= need[c] for c in letters):
                # The first end that covers t gives the shortest window from this start.
                if end - start + 1 < best_len:
                    best_start, best_len = start, end - start + 1
                break
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

Gleitendes Fenster, das jeden Buchstaben überprüft

Idee

Das Hinzufügen von Zeichen zu einem abdeckenden Fenster sorgt dafür, dass es abdeckend bleibt, und das Entfernen von Zeichen aus einem Fenster, das etwas nicht enthält, sorgt dafür, dass es weiterhin etwas nicht enthält. Wenn sich der Start also nach rechts bewegt, bewegt sich das Ende des kürzesten abdeckenden Fensters niemals nach links.

Kein Fenster wird übersehen. Betrachte das beste Fenster von L bis R. Damit left L passiert, bevor right R erreicht, müsste ein kürzeres Fenster ab L t abdecken. Wenn right also R erreicht, bewegt das Verkleinern left bis L und erfasst es.

Jeder Rand bewegt sich höchstens n Mal, aber jede Prüfung liest bis zu u Zählwerte: O(n·u).

Algorithmus

Zähle die Häufigkeit der Zeichen, die t verlangt; setze left = 0 und die beste Länge auf n+1.
Füge für jedes right s[right] zu den Häufigkeiten im Fenster hinzu.
Solange jedes Zeichen aus t ausreichend oft vorkommt, speichere das Fenster, wenn es strikt kürzer ist, entferne s[left] und erhöhe left.
Gib das beste Fenster zurück oder "", wenn die beste Länge weiterhin n+1 beträgt.

def minWindow(s, t):
    need = [0] * 128  # copies of each character code that t asks for
    for ch in t:
        need[ord(ch)] += 1
    letters = [c for c in range(128) if need[c] > 0]
    have = [0] * 128  # counts inside s[left..right]

    def covers():
        for c in letters:
            if have[c] < need[c]:
                return False
        return True

    left = 0
    best_start, best_len = 0, len(s) + 1
    for right in range(len(s)):
        have[ord(s[right])] += 1  # expand on the right
        while covers():  # shrink from the left while the window still covers t
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1
            have[ord(s[left])] -= 1
            left += 1
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

Gleitendes Fenster mit einem Fehlzähler

Idee

Ersetze die Suche durch eine einzige Zahl. Sei need[c] die Anzahl der Vorkommen von c, die t verlangt, abzüglich der Vorkommen im Fenster; ein negativer Wert bedeutet überschüssige Vorkommen. Sei missing die Anzahl der Vorkommen, die dem Fenster noch fehlen, anfangs also die Länge von t. Das Fenster enthält t genau dann, wenn missing 0 ist.

Ein Zeichen, das hinzukommt, während sein need größer als 0 ist, füllt eine Lücke, also sinkt missing. Wenn durch das Entfernen eines Zeichens need auf einen Wert größer als 0 steigt, entsteht eine Lücke, also steigt missing. Überschüssige Vorkommen ändern daran nichts. Bei banana mit t = aan erreicht missing bei bana erstmals 0, und wenn das überschüssige b entfernt wird, enthält ana t weiterhin.

Jedes Zeichen kommt einmal hinzu und wird einmal entfernt, jeweils mit konstantem Aufwand: Laufzeit O(n + m) und eine Tabelle mit 128 Zählern.

Algorithmus

Fülle need mit den Häufigkeiten von t; setze missing auf die Länge von t, left = 0 und die beste Länge auf n+1.
Für jedes right: Wenn need[s[right]] größer als 0 ist, verringere missing; verringere dann need[s[right]].
Solange missing 0 ist, speichere das Fenster, wenn es strikt kürzer ist. Erhöhe need[s[left]]; wenn es jetzt größer als 0 ist, erhöhe missing. Bewege left weiter.
Gib das beste Fenster zurück oder "", wenn die beste Länge immer noch n+1 ist.

def minWindow(s, t):
    # need[c]: copies of c that t asks for minus copies inside the window.
    # Positive means the window still lacks c; negative means it holds spares.
    need = [0] * 128
    for ch in t:
        need[ord(ch)] += 1
    missing = len(t)  # characters of t the window does not cover yet
    left = 0
    best_start, best_len = 0, len(s) + 1
    for right in range(len(s)):
        c = ord(s[right])
        if need[c] > 0:  # this copy fills a gap
            missing -= 1
        need[c] -= 1
        while missing == 0:  # the window covers t: record it, then shrink
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1
            c = ord(s[left])
            need[c] += 1
            if need[c] > 0:  # gave away a copy t needs
                missing += 1
            left += 1
    if best_len > len(s):
        return ""
    return s[best_start:best_start + best_len]

Stolperfallen und Grenzfälle

Buchstaben statt Vorkommen zählen. t = aan benötigt zwei as, daher reicht ban nicht aus.
missing für jedes Zeichen ändern, das hinzukommt oder wegfällt. Ein überschüssiges a wird dann mitgezählt, und missing kann 0 erreichen, obwohl dem Fenster das n fehlt.
Das beste Fenster bei gleicher Länge ersetzen. Im zweiten Beispiel wird dadurch das ana an Index 3 zurückgegeben.
n als Länge für „nicht gefunden“ verwenden. Wenn die Antwort ganz aus s besteht, ist ihre Länge ebenfalls n; beginne mit n+1.
Eine Tabelle mit 26 Einträgen verwenden, indiziert durch c - 'a'. Großbuchstaben wie im dritten Beispiel liegen außerhalb davon.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von „Minimum Window Substring“?

Das Fenster mit fehlendem Zähler läuft in O(n + m) Zeit, wobei n und m die Längen von s und t sind. Beim Erstellen der Tabelle wird t einmal durchlaufen, und jedes Zeichen von s tritt höchstens einmal in das Fenster ein und verlässt es höchstens einmal. Der zusätzliche Speicherbedarf beträgt einen Zähler pro Zeichencode.

Warum bewegt sich die linke Kante nie wieder zurück?

Die linke Grenze überschreitet eine Position erst, nachdem das dort beginnende Fenster t abgedeckt hat, und dieses Fenster war das kürzeste, das von diesem Startpunkt aus alles abdeckte. Jedes Fenster von dort, das später endet, ist länger, sodass ein Zurückgehen niemals eine bessere Antwort finden kann.

Worin unterscheidet sich Minimum Window Substring davon, ein Anagramm in einer Zeichenkette zu finden?

Ein Anagramm enthält genau die Buchstaben von t, daher hat sein Fenster eine feste Länge von m und verschiebt sich Schritt für Schritt. Hier sind zusätzliche Zeichen erlaubt, daher ist die Länge Teil der Antwort: Das Fenster wächst, bis es t abdeckt, und schrumpft, solange es das weiterhin tut.

def minWindow(s, t):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

s = "mappingtheplan"
t = "nap"

Erwartete Ausgabe

"plan"

Minimum Window Substring

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Vergrößere ein Fenster von jedem Startpunkt aus

Gleitendes Fenster, das jeden Buchstaben überprüft

Gleitendes Fenster mit einem Fehlzähler

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben