Minimum Window Substring

Q: Was zählt der fehlende Zähler?

Es ist die Anzahl der Zeichenkopien, die t benötigt und die das Fenster noch nicht enthält, also die Summe der positiven Werte in need . Sie beginnt bei der Länge von t und ist genau dann 0, wenn das Fenster t abdeckt. Überschüssige Kopien ändern sie nie. Dadurch kann ein einziger Vergleich das Durchlaufen aller Buchstaben ersetzen.

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

Ein Anagramm besteht genau aus den Buchstaben von t und keinen anderen, daher hat das Fenster eine feste Länge von m und wird schrittweise verschoben. Hier kann das Fenster zusätzliche Zeichen enthalten, daher ist seine Länge Teil der Antwort: Es wächst rechts, bis es t abdeckt, und schrumpft links, solange es das weiterhin tut.

SchwerSliding Window Hashing

+10

Du erhältst zwei Zeichenfolgen, s und t. Finde die kürzeste Teilzeichenfolge von s, also eine Folge aufeinanderfolgender Zeichen, die jedes Zeichen von t enthält, wobei Wiederholungen mitgezählt werden: Wenn t einen Buchstaben zweimal enthält, muss die Teilzeichenfolge ihn mindestens zweimal enthalten. Die Reihenfolge spielt keine Rolle, und die Teilzeichenfolge darf auch andere Zeichen enthalten.

Wenn mehrere Teilzeichenfolgen dieselbe kürzeste Länge haben, gib die am weitesten links stehende zurück. Wenn keine Teilzeichenfolge von s alle Zeichen von t enthält, gib eine leere Zeichenfolge zurück.

Funktion

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

sstring: die Zeichenkette, 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 nur 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 existiert, ist sie "".

Beispiele

Eingabe: s = "mappingtheplan"t = "nap"
Ausgabe: "plan"
Erklärung: Von links gelesen ist das erste Fenster, das ein n, ein a und ein p enthält, appin und fünf Zeichen lang. plan am Ende enthält alle drei in vier Zeichen, und kein Abschnitt aus drei Zeichen enthält sie.

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 einzige C in Coddy ist großgeschrieben, und Groß- und Kleinbuchstaben sind unterschiedliche Zeichen. Kein Teilstring enthält ein kleingeschriebenes c, daher ist die Antwort die leere Zeichenfolge.

+17 versteckte Tests beim Einreichen

Weiterführende Frage

Wenn t nur wenige Buchstaben enthält und s lang ist, können die meisten Teile von s nie relevant sein. Kannst du dafür sorgen, dass das Fenster nur zwischen den Positionen springt, an denen ein Buchstabe aus t steht?

Tipps

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

0 von 3 geöffnet

Lösung

Die Antwort hängt davon ab, wie oft jedes Zeichen in einem Fenster vorkommt, nicht von seiner Reihenfolge, und das beste Fenster kann an beliebiger Stelle beginnen. Jeden möglichen Startpunkt mit jedem möglichen Endpunkt auszuprobieren, bedeutet O(n²) Fenster. Der entscheidende Kniff ist ein Fenster, dessen Ränder sich nur nach vorne bewegen: Der rechte Rand vergrößert es, bis es t abdeckt, der linke Rand verkleinert es, solange es t weiterhin abdeckt, und ein Zähler für fehlende Zeichen verrät dir in einem einzigen Schritt, ob es t abdeckt.

Erweitere ein Fenster von jedem Startpunkt aus

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

Idee

Lege fest, wo die Teilzeichenfolge beginnt. Vergrößere sie dann Zeichen für Zeichen, zähle dabei jedes enthaltene Zeichen und prüfe nach jedem Schritt, ob sie t abdeckt: Für jeden der u verschiedenen Buchstaben, die t verwendet, muss das Fenster mindestens so viele Vorkommen enthalten wie t. Das erste Ende, das diese Bedingung erfüllt, ergibt das kürzeste abdeckende Fenster für diesen Start, denn jedes kürzere Fenster vom selben Start aus wurde zuerst geprüft und hat die Bedingung nicht erfüllt. Beende die Suche an dieser Stelle.

Gehe so für jeden Start vor und behalte das kürzeste Fenster. Die Starts werden von links nach rechts ausprobiert, und ein Fenster ersetzt das bisher beste nur, wenn es strikt kürzer ist. Daher bleibt bei gleich kurzen Fenstern das am weitesten links liegende erhalten.

Bei langen Fenstern oder wenn kein passendes Fenster vorhanden ist, ist das langsam. Wenn das einzige Z in s ganz am Ende steht und t ein solches Zeichen verlangt, durchsucht jeder Start die Zeichen bis ganz zum Ende: etwa n²/2 Schritte, also 1.25 × 10^9 für n = 5 × 10^4, wobei jeder Schritt bis zu 52 Buchstaben prüft. Dasselbe passiert, wenn es überhaupt kein Fenster gibt.

Algorithmus

Zähle, wie oft t jedes Zeichen verlangt, und liste die verwendeten Buchstaben auf.
Leere für jedes start eine Zähltabelle und bewege end von start bis zum Ende von s, wobei du s[end] zur Tabelle hinzufügst.
Prüfe nach jeder Ergänzung jeden Buchstaben von t. Wenn das Fenster von jedem Buchstaben genügend enthält, vergleiche seine Länge mit der bisher besten, behalte es, wenn es strikt kürzer ist, und erweitere das Fenster nicht weiter.
Gib nach allen Startpositionen 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

Zwei Tatsachen machen den Neustart überflüssig. Wenn man einem Fenster, das t abdeckt, Zeichen hinzufügt, deckt es weiterhin t ab, und wenn man aus einem Fenster, das etwas nicht enthält, Zeichen entfernt, enthält es weiterhin nichts davon. Wenn sich der Anfang also nach rechts bewegt, kann das Ende des kürzesten abdeckenden Fensters nur an derselben Stelle bleiben oder sich nach rechts bewegen. Beide Grenzen können gemeinsam vorwärts wandern, und keine bewegt sich jemals zurück.

Bewege right über s und füge jedes Zeichen einer Tabelle mit Häufigkeiten hinzu. Immer wenn das Fenster t abdeckt, ist es ein Kandidat: Speichere es, wenn es kürzer als das bisher beste ist, entferne dann s[left], bewege left weiter und prüfe erneut. Wiederhole das, bis das Fenster t nicht mehr abdeckt, und fahre dann damit fort, es nach rechts zu vergrößern.

Kein Fenster wird übersehen. Betrachte das beste Fenster von L bis R. Wenn sich left weiter als L bewegt hätte, bevor right R erreicht, hätte ein Fenster von L mit einem Ende vor R t abgedeckt und wäre kürzer als das beste gewesen. Wenn right also R erreicht, bewegt die Verkleinerungsschleife left bis L und speichert das beste Fenster. Jede Grenze bewegt sich höchstens n Mal, aber bei jeder Prüfung werden bis zu u Häufigkeiten abgefragt, eine für jeden Buchstaben, den t verwendet, obwohl sich seit der letzten Prüfung nur eine Häufigkeit geändert hat.

Algorithmus

Zähle die benötigten Vorkommen der Zeichen aus t und liste sie auf; beginne mit einem leeren Fenster, left = 0, und einer besten Länge von n+1.
Gehe mit right über jeden Index und füge s[right] zu den Zählwerten des Fensters hinzu.
Solange jedes Zeichen aus t im Fenster ausreichend oft vorkommt, speichere das Fenster, wenn es strikt kürzer als das bisher beste ist, entferne s[left] aus den Zählwerten und rücke left weiter.
Gib das beste Fenster zurück oder "", wenn die beste Länge immer noch 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]

Gleitfenster mit einem Fehlzähler

Idee

Behalte dasselbe Fenster bei und ersetze die Prüfung durch eine einzige Zahl. Sei need[c] die Anzahl der Vorkommen von c, die t verlangt, abzüglich der Anzahl der Vorkommen im Fenster. Ein positiver Wert bedeutet, dass dem Fenster noch einige fehlen, ein negativer, dass es überschüssige enthält. Sei missing die Gesamtzahl der Vorkommen, die dem Fenster fehlen; sie beginnt mit der Länge von t. Das Fenster enthält t genau dann, wenn missing 0 ist.

Die Aktualisierung kostet einen Schritt. Wenn s[right] hinzukommt und need dafür größer als 0 ist, schließt es eine Lücke, also sinkt missing um eins; in jedem Fall sinkt need um eins und kann als Überschuss unter 0 fallen. Wenn s[left] das Fenster verlässt, steigt need um eins. Ist es nun größer als 0, hat das Fenster ein Vorkommen abgegeben, das t benötigte, also steigt missing um eins. Überschüsse kommen und gehen, ohne missing zu verändern.

Verfolge s = banana, t = aan: Anfangs ist need für a 2 und für n 1, und missing ist 3. b wird nicht benötigt. Das erste a senkt missing auf 2, das n auf 1 und das zweite a auf 0, sodass bana t enthält. Beim Verkleinern fällt das überschüssige b weg und ana bleibt übrig, drei Zeichen, das neue beste Ergebnis. Wenn dieses a entfernt wird, steigt missing wieder auf 1. Das letzte a ergibt erneut ein passendes Fenster mit nana, das auf das zweite ana verkleinert wird. Es ist nicht kürzer, also bleibt das linkeste ana erhalten.

Jedes Zeichen von s kommt einmal ins Fenster und verlässt es höchstens einmal, und jede Bewegung kostet eine konstante Menge an Arbeit. Beim Erstellen von need wird t einmal durchlaufen. Der gesamte Ablauf benötigt O(n + m); als zusätzlicher Speicher dient nur eine Tabelle mit 128 Zählern.

Algorithmus

Fülle need mit den Häufigkeiten von t und 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 als das beste ist. Erhöhe dann need[s[left]]; wenn es nun größer als 0 ist, erhöhe missing. Bewege left weiter.
Gib das beste Fenster zurück oder "", wenn die beste Länge weiterhin 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

Die meisten falschen Antworten zählen das Falsche oder halten das Fenster zum falschen Zeitpunkt fest.

Buchstaben statt Vorkommen zählen. t = aan benötigt zwei a, daher deckt ban es nicht ab.
missing für jedes Zeichen verringern, das hinzukommt. Ein drittes a ist überschüssig; wenn es missing verringert, erreicht der Zähler 0, obwohl dem Fenster noch das n fehlt. Verringere den Wert nur, wenn need größer als 0 war.
missing für jedes Zeichen erhöhen, das entfernt wird. Wenn ein überschüssiges Zeichen wegfällt, deckt das Fenster t weiterhin ab; erhöhe den Wert nur, wenn need größer als 0 wird.
Das Fenster nach der Verkleinerungsschleife festhalten. Dann deckt es t nicht mehr ab. Halte es innerhalb der Schleife fest, bevor du s[left] entfernst.
Das beste Fenster ersetzen, wenn das neue genauso lang ist. Dadurch wird das am weitesten rechts liegende der kürzesten Fenster zurückgegeben; verwende einen strikten Kleiner-als-Vergleich.
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, damit sich die beiden Fälle unterscheiden.
Eine Tabelle mit 26 Einträgen verwenden, die über c - 'a' indiziert wird. Großbuchstaben liegen außerhalb davon. Verwende einen Eintrag pro Zeichencode.

Häufige Fragen4

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

Das Sliding Window mit einem Zähler für fehlende Zeichen benötigt eine Laufzeit von O(n + m), wobei n und m die Längen von s und t sind. Beim Erstellen der Tabelle wird t einmal gelesen, und jedes Zeichen von s gelangt höchstens einmal in das Fenster und verlässt es höchstens einmal, wobei jeder Schritt konstante Kosten verursacht. Der zusätzliche Speicherbedarf besteht aus einer Tabelle mit einem Zähler pro Zeichencode, deren Größe nicht mit der Eingabe wächst.

Warum bewegt sich der linke Rand nie zurück?

Der linke Rand bewegt sich erst dann über eine Position hinaus, wenn ein dort beginnendes Fenster t abgedeckt hat, und das war das kürzeste abdeckende Fenster ab diesem Startpunkt. Jedes Fenster, das dort beginnt und später endet, ist länger, sodass ein Zurückgehen niemals eine bessere Antwort finden könnte. Deshalb bewegen sich beide Ränder jeweils nur einmal vorwärts, und der Aufwand bleibt linear.

Was zählt der fehlende Zähler?

Es ist die Anzahl der Zeichenkopien, die t benötigt und die das Fenster noch nicht enthält, also die Summe der positiven Werte in need. Sie beginnt bei der Länge von t und ist genau dann 0, wenn das Fenster t abdeckt. Überschüssige Kopien ändern sie nie. Dadurch kann ein einziger Vergleich das Durchlaufen aller Buchstaben ersetzen.

Wie unterscheidet sich Minimum Window Substring davon, ein Anagramm in einer Zeichenfolge zu finden?

Ein Anagramm besteht genau aus den Buchstaben von t und keinen anderen, daher hat das Fenster eine feste Länge von m und wird schrittweise verschoben. Hier kann das Fenster zusätzliche Zeichen enthalten, daher ist seine Länge Teil der Antwort: Es wächst rechts, bis es t abdeckt, und schrumpft links, solange es das weiterhin tut.

Python

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

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

s = "mappingtheplan"
t = "nap"

Erwartet

"plan"

Minimum Window Substring

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Erweitere ein Fenster von jedem Startpunkt aus

Gleitendes Fenster, das jeden Buchstaben überprüft

Gleitfenster mit einem Fehlzähler

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben