Minimum Window Substring

Q: Caka złożoność czasowa problemu Minimum Window Substring?

Okno brakujących liczników działa w czasie O(n + m) , gdzie n i m to długości s i t . Budowanie tablicy odczytuje t raz, a każdy znak s wchodzi do okna i je opuszcza najwyżej raz. Dodatkowa pamięć to jeden licznik na każdy kod znaku.

Q: Czym różni się Minimum Window Substring od wyszukiwania anagramu w ciągu znaków?

Anagram zawiera dokładnie te same litery co t , więc jego okno ma stałą długość m i przesuwa się o jeden krok naraz. Tutaj dozwolone są dodatkowe znaki, więc długość jest częścią odpowiedzi: okno rośnie, aż obejmie t , i zmniejsza się, dopóki nadal je obejmuje.

TrudnePrzesuwane okno Haszowanie

+10

Otrzymujesz dwa ciągi znaków: s i t. Znajdź najkrótszy podciąg s, który zawiera każdy znak z t, uwzględniając powtórzenia: jeśli t zawiera daną literę dwa razy, podciąg musi zawierać ją co najmniej dwa razy. Kolejność nie ma znaczenia, a mogą się w nim znaleźć również inne znaki.

Jeśli kilka podciągów ma minimalną długość, zwróć ten najbardziej wysunięty w lewo. Jeśli żaden nie zawiera wszystkich znaków z t, zwróć pusty ciąg znaków.

Funkcja

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

sstring: ciąg znaków, którego szukamy
tstring: znaki, które okno musi zawierać, wraz z powtórzeniami
Zwracastring: najkrótszy, a w przypadku remisu najbardziej lewy fragment s zawierający wszystkie znaki t albo pusty ciąg

Ograniczenia

1 ≤ s.length ≤ 5 × 10⁴
1 ≤ t.length ≤ 10⁴
s i t zawierają wyłącznie angielskie litery. Wielkie i małe litery to różne znaki.
Gdy kilka podciągów jest najkrótszych, odpowiedzią jest ten najbardziej po lewej; gdy nie ma żadnego, jest nią "".

Przykłady

Wejście: s = "mappingtheplan"t = "nap"
Wyjście: "plan"
Wyjaśnienie: Pierwsze od lewej okno zawierające n, a i p to appin — pięć znaków. plan zawiera wszystkie trzy w czterech znakach, a żaden ciąg trzech znaków tego nie robi.

Wejście: s = "banana"t = "aan"
Wyjście: "ana"
Wyjaśnienie: t wymaga dwóch kopii a i jednego n. ana na indeksie 1 zawiera dokładnie tyle. Drugie ana zaczyna się na indeksie 3, a wygrywa to najbardziej po lewej.

Wejście: s = "Coddy"t = "cd"
Wyjście: ""
Wyjaśnienie: Litera C w nazwie Coddy jest wielka, czyli inna niż c. Żaden podciąg nie zawiera małej litery c, więc odpowiedzią jest pusty ciąg znaków.

Pytanie dodatkowe

Gdy t zawiera niewiele liter, a s jest długie, większość s nigdy nie ma znaczenia. Czy możesz sprawić, by okno przeskakiwało tylko między pozycjami, w których znajduje się litera z t?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Liczą się tylko liczebności znaków w oknie, a nie ich kolejność. Przesuwaj prawą krawędź, aż okno obejmie t, a następnie lewą, dopóki nadal je obejmuje; żadna z krawędzi nie cofa się. Licznik brakujących znaków pozwala za jednym razem sprawdzić, czy okno obejmuje t.

Rozwijaj okno z każdego początku

Poprawne, ale nie kończy się na największych testach

Intuicja

Ustal początek i powiększaj okno po jednym znaku, zliczając wystąpienia każdego znaku. Po każdym kroku sprawdzaj każdą z u liter używanych przez t. Pierwszy koniec, który spełnia warunek, daje najkrótsze okno zawierające wymagane znaki dla tego początku, więc na nim zakończ. Początki rozpatruj od lewej do prawej, a najlepszy wynik zastępuj tylko oknem ściśle krótszym, więc przy remisie pozostaje to najbardziej na lewo.

Jeśli żadne okno nie istnieje, każdy początek wymaga odczytania do końca s: około n²/2 kroków, czyli 1.25 × 10^9 dla n = 5 × 10^4.

Algorytm

Policz wystąpienia każdej litery, o którą prosi t.
Dla każdego start wyczyść tabelę zliczeń i przesuwaj end w prawo, dodając s[end].
Gdy okno zawiera wystarczającą liczbę każdej litery, zachowaj je, jeśli jest ściśle krótsze od najlepszego, i przejdź do następnego początku.
Zwróć najlepsze okno lub "", jeśli żadne nie zawierało t.

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]

Okno przesuwne, które sprawdza każdą literę

Intuicja

Dodawanie znaków do okna, które pokrywa wymagane znaki, sprawia, że nadal je pokrywa, a usuwanie znaków z okna, któremu czegoś brakuje, sprawia, że nadal mu czegoś brakuje. Dlatego gdy początek przesuwa się w prawo, koniec najkrótszego okna pokrywającego wymagane znaki nigdy nie przesuwa się w lewo.

Żadne okno nie zostaje pominięte. Weźmy najlepsze okno od L do R. Aby left minęło L, zanim right dotrze do R, krótsze okno zaczynające się od L musiałoby pokrywać t. Gdy więc right dotrze do R, zwężanie przesuwa left do L i zapisuje to okno.

Każdy koniec przesuwa się najwyżej n razy, ale każde sprawdzenie odczytuje do u liczników: O(n·u).

Algorytm

Policz, ile kopii wymaga t; ustaw left = 0, a najlepszą długość na n+1.
Dla każdego right dodaj s[right] do liczników znaków w oknie.
Dopóki każda litera z t ma wystarczającą liczbę kopii, zapisz okno, jeśli jest ściśle krótsze, usuń s[left] i przesuń left do przodu.
Zwróć najlepsze okno albo "", jeśli najlepsza długość nadal wynosi n+1.

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]

Okno przesuwne z licznikiem brakujących elementów

Intuicja

Zastąp skanowanie jedną liczbą. Niech need[c] oznacza liczbę kopii c, których wymaga t, pomniejszoną o liczbę kopii w oknie; wartość ujemna oznacza nadmiar. Niech missing oznacza liczbę kopii, których w oknie wciąż brakuje — początkowo jest równa długości t. Okno dokładnie pokrywa t, gdy missing wynosi 0.

Znak, który trafia do okna, gdy jego need jest większe od 0, wypełnia lukę, więc missing maleje. Usunięcie znaku, które zwiększa jego need powyżej 0, tworzy lukę, więc missing rośnie. Nadmiarowe znaki nie mają na to wpływu. Dla banana przy t = aan wartość missing po raz pierwszy osiąga 0 dla bana, a usunięcie nadmiarowego b pozostawia ana, które nadal pokrywa t.

Każdy znak jest dodawany i usuwany dokładnie raz przy stałym koszcie: czas O(n + m) i jedna tablica 128 liczników.

Algorytm

Wypełnij need licznikami wystąpień t; ustaw missing na długość t, left = 0, a najlepszą długość na n+1.
Dla każdej wartości right: jeśli need[s[right]] jest większe od 0, zmniejsz missing; następnie zmniejsz need[s[right]].
Dopóki missing wynosi 0, zapisz okno, jeśli jest ściśle krótsze. Zwiększ need[s[left]]; jeśli teraz jest większe od 0, zwiększ missing. Przesuń left do przodu.
Zwróć najlepsze okno albo "", jeśli najlepsza długość nadal wynosi n+1.

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]

Pułapki i przypadki brzegowe

Liczenie liter zamiast ich wystąpień. t = aan wymaga dwóch a, więc ban nie wystarczy.
Zmienianie missing dla każdego znaku, który wchodzi do okna lub je opuszcza. Zapasowe a zostaje wtedy policzone, a missing może osiągnąć 0, mimo że w oknie brakuje n.
Zastępowanie najlepszego okna oknem o tej samej długości. W drugim przykładzie zwróci to ana na indeksie 3.
Używanie n jako długości oznaczającej „nie znaleziono”. Gdy odpowiedzią jest całe s, jego długość również wynosi n; zacznij od n+1.
Tablica 26 miejsc indeksowanych przez c - 'a'. Wielkie litery, jak w trzecim przykładzie, wykraczają poza jej zakres.

Najczęstsze pytania3

Caka złożoność czasowa problemu Minimum Window Substring?

Okno brakujących liczników działa w czasie O(n + m), gdzie n i m to długości s i t. Budowanie tablicy odczytuje t raz, a każdy znak s wchodzi do okna i je opuszcza najwyżej raz. Dodatkowa pamięć to jeden licznik na każdy kod znaku.

Dlaczego lewa krawędź nigdy nie przesuwa się z powrotem?

Lewa krawędź mija daną pozycję dopiero wtedy, gdy zaczynające się w niej okno objęło t, a to okno było najkrótszym obejmującym je oknem zaczynającym się w tym miejscu. Każde okno zaczynające się tam i kończące się później jest dłuższe, więc cofanie się nigdy nie pozwoli znaleźć lepszej odpowiedzi.

Czym różni się Minimum Window Substring od wyszukiwania anagramu w ciągu znaków?

Anagram zawiera dokładnie te same litery co t, więc jego okno ma stałą długość m i przesuwa się o jeden krok naraz. Tutaj dozwolone są dodatkowe znaki, więc długość jest częścią odpowiedzi: okno rośnie, aż obejmie t, i zmniejsza się, dopóki nadal je obejmuje.

def minWindow(s, t):
    # Napisz tutaj kod

Test #1

Test #2

Test #3

Argumenty

s = "mappingtheplan"
t = "nap"

Oczekiwany wynik

"plan"

Minimum Window Substring

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Rozwijaj okno z każdego początku

Okno przesuwne, które sprawdza każdą literę

Okno przesuwne z licznikiem brakujących elementów

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania