Longest Substring Without Repeating Characters

Q: Jaka jest różnica między podciągiem a podsekwencją?

Podciąg to blok sąsiadujących ze sobą znaków, taki jak ode w coddycode . Podciąg złożony może pomijać znaki, tak jak cdy . To zadanie dotyczy podciągu, dlatego sprawdza się okno z dwoma krawędziami.

ŚredniePrzesuwane okno Haszowanie

+10

Otrzymujesz ciąg znaków s. Znajdź najdłuższy podciąg, czyli ciąg sąsiadujących ze sobą znaków, w którym żaden znak się nie powtarza, i zwróć jego długość.

Wielkie i małe litery są traktowane jako różne znaki, więc a i A nie są powtórzeniem.

Funkcja

lengthOfLongestSubstring(s: string) → integer

sstring: ciąg znaków do wyszukania
Zwracainteger: długość najdłuższego podciągu bez powtarzających się znaków

Ograniczenia

1 ≤ s.length ≤ 5 × 10⁴
s zawiera wyłącznie litery alfabetu angielskiego (małe i wielkie) oraz cyfry.
Wielkie i małe litery to różne znaki.

Przykłady

Wejście: s = "coddycode"
Wyjście: 5
Wyjaśnienie: ycode zawiera pięć różnych znaków. Dodanie d przed nim daje dycode, w którym d występuje dwa razy, a żaden inny ciąg składający się z pięciu lub więcej znaków nie pozwala uniknąć powtórzenia.

Wejście: s = "racecar"
Wyjście: 4
Wyjaśnienie: Zarówno race, jak i ecar składają się z czterech różnych liter. W każdym ciągu pięciu liter ta sama litera występuje dwa razy.

Wejście: s = "a1b2a3b"
Wyjście: 5
Wyjaśnienie: Cyfry również liczą się jako znaki, więc 1b2a3 ma ich pięć. Oba ciągi o długości sześciu zawierają drugie a lub drugie b.

Pytanie dodatkowe

Co byś zmienił, gdyby s mogło zawierać dowolny znak Unicode zamiast liter i cyfr?

Rozwiązanie

Utrzymuj okno: dwa końce obejmujące fragment bez powtarzających się znaków. Prawy koniec odczytuje każdy znak raz, a lewy przesuwa się tylko do przodu, więc jedno przejście znajduje dla każdego końca najdłuższy fragment bez powtórzeń, który się na nim kończy.

Sprawdź każdy podciąg

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

Intuicja

Wypróbuj każdy początek i koniec, a następnie sprawdź każdy podciąg, dodając jego znaki do zbioru, aż któryś już się w nim znajdzie. Każdy kandydat zostaje sprawdzony, więc najdłuższy poprawny nie może zostać pominięty.

Istnieje około n²/2 podciągów, czyli 1.25 × 10^9 dla n = 5 × 10^4, a sprawdzenie może odczytać do n znaków: O(n³). Tutaj sprawdzanie kończy się po najwyżej 63 znakach, ponieważ ciąg zawiera tylko 62 różne znaki, ale wciąż pozostaje ponad miliard sprawdzeń.

Algorytm

Ustaw best na 0.
Dla każdego indeksu początkowego przejdź przez wszystkie indeksy końcowe, od początku do końca ciągu znaków.
Dodawaj po kolei znaki podciągu do pustego zbioru i zatrzymaj się przy pierwszym znaku, który już się w nim znajduje.
Jeśli żaden znak się nie powtórzył, a podciąg jest dłuższy niż best, zapisz jego długość.
Zwróć best.

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

Przesuwne okno ze zbiorem

Intuicja

Jeśli abc nie zawiera powtórzeń, sprawdzenie abcd wymaga jednego pytania: czy d znajduje się wśród a, b i c? Zbiór znaków w oknie odpowiada na nie od razu.

Przesuwaj right krok po kroku. Jeśli nowy znak znajduje się w zbiorze, usuwaj znaki z lewej strony, aż zniknie jego wcześniejsze wystąpienie, a następnie dodaj go i zmierz długość. Usuwasz znaki tylko wtedy, gdy musisz, więc dla każdego right okno jest najdłuższym ciągiem bez powtórzeń, który kończy się w tym miejscu, a najlepszy podciąg może kończyć się gdziekolwiek. Każdy znak trafia do zbioru raz i opuszcza go najwyżej raz: O(n).

Algorytm

Zacznij od pustego zbioru, left = 0 i best = 0.
Przesuwaj right przez wszystkie indeksy.
Dopóki s[right] znajduje się w zbiorze, usuń s[left] i przesuń left o jeden krok do przodu.
Dodaj s[right] do zbioru.
Jeśli right - left + 1 jest większe niż best, zapisz tę wartość.
Zwróć best.

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

Przesuwne okno przeskakujące do indeksu ostatniego wystąpienia

Intuicja

Już wiesz, gdzie musi trafić left: tuż za wcześniejszą kopią nowego znaku. Zapisz indeks ostatniego wystąpienia każdego znaku w mapie lub tablicy z jednym miejscem na każdy kod znaku, a left przeskoczy tam w jednym kroku.

Przeskakuj tylko wtedy, gdy ten indeks znajduje się na pozycji left lub dalej. Starsza kopia jest już poza oknem, a przeskoczenie do niej cofnęłoby left. Okno na każdym kroku jest takie samo jak to tworzone przez wersję zbiorem, a teraz obsługa każdego znaku wymaga jednego wyszukania, jednego porównania i jednego zapisu.

Algorytm

Utwórz pustą mapę przypisującą znaki do ich ostatnich indeksów i ustaw left = 0 oraz best = 0.
Przesuwaj right przez każdy indeks, odczytując znajdujący się tam znak ch.
Jeśli ch był ostatnio widziany na indeksie równym left lub większym, ustaw left na ten indeks plus jeden.
Zapisz right jako ostatni indeks znaku ch.
Jeśli right - left + 1 jest większe niż best, zapisz tę wartość.
Zwróć best.

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

Pułapki i przypadki brzegowe

Przesunięcie left wstecz. W abba wcześniejsze a o indeksie 0 znajduje się już poza oknem, gdy docierasz do ostatniego a. Przeskoczenie do indeksu 1 ponownie włącza drugie b do okna i daje wynik 3 zamiast 2.
Liczenie długości okna jako right - left. Oba końce znajdują się w oknie, więc dodaj jeden.
Najpierw zamiana całego ciągu na małe litery. a i A to tutaj różne znaki, więc aA ma długość 2.
Mierzenie długości tylko wtedy, gdy pojawi się powtórzenie. Ciąg bez powtórzeń, taki jak z, nigdy tego nie wywoła, a wynikiem będzie 0.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu najdłuższego podciągu bez powtarzających się znaków?

Przesuwane okno działa w czasie O(n), gdzie n to długość ciągu znaków: prawa krawędź odczytuje każdy znak raz, a lewa krawędź przesuwa się tylko do przodu. Dodatkowe zużycie pamięci wynosi O(k), gdzie k to liczba różnych znaków, które może zawierać ciąg — tutaj 62.

Czy do przechowywania ostatnich indeksów użyć mapy haszującej czy tablicy?

Oba rozwiązania mają złożoność czasową O(n). Przy małym, ustalonym zestawie znaków, takim jak tutaj, tablica indeksowana kodem znaku pozwala uniknąć haszowania i działa szybciej.

Jaka jest różnica między podciągiem a podsekwencją?

Podciąg to blok sąsiadujących ze sobą znaków, taki jak ode w coddycode. Podciąg złożony może pomijać znaki, tak jak cdy. To zadanie dotyczy podciągu, dlatego sprawdza się okno z dwoma krawędziami.

def lengthOfLongestSubstring(s):
    # Wpisz tutaj kod

Test #1

Test #2

Test #3

Argument

s = "coddycode"

Oczekiwany wynik

Longest Substring Without Repeating Characters

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Sprawdź każdy podciąg

Przesuwne okno ze zbiorem

Przesuwne okno przeskakujące do indeksu ostatniego wystąpienia

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania