Longest Repeating Character Replacement

+10

Otrzymujesz ciąg znaków s składający się z wielkich liter angielskiego alfabetu oraz liczbę całkowitą k. Możesz wybrać co najwyżej k pozycji w s i zmienić literę na każdej z nich na dowolną inną wielką literę.

Zwróć długość najdłuższego podciągu spójnego, czyli ciągu sąsiadujących liter, który po zmianach składa się z jednej powtarzającej się litery.

Funkcja

characterReplacement(s: string, k: integer) → integer

sstring: ciąg wielkich liter
kinteger: najwięcej liter, które możesz zmienić
Zwracainteger: długość najdłuższego ciągu jednakowych liter, jaki możesz utworzyć

Ograniczenia

1 ≤ s.length ≤ 5 × 10⁴
s zawiera wyłącznie wielkie litery alfabetu angielskiego.
0 ≤ k ≤ s.length

Przykłady

Wejście: s = "BAAACAB"k = 1
Wyjście: 5
Wyjaśnienie: Zmiana C na A sprawia, że indeksy od 1 do 5 dają AAAAA. Oba sześcioliterowe okna zawierają B i C, więc wymagają dwóch zmian.

Wejście: s = "AABBBAB"k = 2
Wyjście: 6
Wyjaśnienie: Indeksy od 1 do 6 zawierają ABBBAB, a zmiana obu liter A daje BBBBBB. Cały ciąg ma tylko cztery litery B spośród siedmiu, więc wymaga trzech zmian.

Pytanie dodatkowe

Co się zmieni, jeśli s może zawierać dowolny znak zamiast 26 wielkich liter?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Zachowaj najczęściej występującą literę podciągu i zmień pozostałe: podciąg o długości len, w którym najczęściej występująca litera pojawia się top razy, wymaga len - top zmian. Okno przesuwne znajduje najdłuższy podciąg spełniający warunek len - top ≤ k w jednym przejściu, ponieważ okna nigdy nie trzeba zmniejszać, a top nigdy nie musi maleć.

Sprawdź każdy podciąg znaków

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

Intuicja

Dla każdego początku zwiększaj koniec o jedną literę, aktualizuj liczniki poszczególnych liter i top, a następnie sprawdzaj len - top ≤ k. Każdy nowy podciąg wymaga jednej aktualizacji zamiast ponownego liczenia, a ponieważ sprawdzany jest każdy podciąg, nie można przeoczyć najdłuższego, który spełnia warunek.

Łańcuch o długości n ma około n²/2 podciągów: 1.25 × 10^9 sprawdzeń dla n = 5 × 10^4.

Algorytm

Ustaw best na 0.
Dla każdego indeksu początkowego wyzeruj 26 liczników i top.
Przesuwaj end od indeksu początkowego do ostatniego indeksu. Dodaj s[end] do jego licznika i zwiększ top, jeśli ten licznik jest teraz największy.
Jeśli end - start + 1 - top ≤ k, zapisz długość, jeśli jest większa niż best.
Zwróć best.

def characterReplacement(s, k):
    n = len(s)
    best = 0
    for start in range(n):
        count = [0] * 26  # letters in s[start..end]
        top = 0           # count of the most common letter there
        for end in range(start, n):
            c = ord(s[end]) - ord('A')
            count[c] += 1
            top = max(top, count[c])
            # Every letter that is not the most common one must change.
            if end - start + 1 - top <= k:
                best = max(best, end - start + 1)
    return best

Jedno przesuwne okno na każdą docelową literę

Intuicja

Najpierw wybierz ostatnią literę. Jeśli cały ciąg ma się składać z liter A, szukasz najdłuższego podciągu zawierającego co najwyżej k liter innych niż A.

Przesuwaj right po ciągu i zliczaj litery inne niż docelowa w oknie. Gdy ich liczba przekroczy k, przesuwaj left do przodu, aż znowu będzie ich k. Okno, które jest zbyt kosztowne, pozostaje takie, gdy je powiększasz, więc left nigdy się nie cofa, a dla każdego right okno jest najdłuższym poprawnym oknem kończącym się w tym miejscu.

Wykonaj to dla wszystkich 26 liter i zachowaj najlepszy wynik: 26 liniowych przejść po ciągu zawierającym do 5 × 10^4 liter. Złożoność pozostaje O(n) tylko dlatego, że alfabet jest mały.

Algorytm

Dla każdej docelowej litery od A do Z rozpocznij okno z left = 0 i others = 0.
Przesuwaj right po ciągu. Jeśli s[right] nie jest docelową literą, zwiększ others o jeden.
Gdy others > k, przesuwaj left do przodu, odejmując jeden, jeśli opuszczająca okno litera nie jest docelową literą.
Zapisz right - left + 1, jeśli ta wartość jest większa niż best.
Po sprawdzeniu wszystkich 26 liter zwróć best.

def characterReplacement(s, k):
    best = 0
    for target in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
        left = 0
        others = 0  # letters in s[left..right] that are not target
        for right in range(len(s)):
            if s[right] != target:
                others += 1
            # Too many letters to change: drop letters from the left.
            while others > k:
                if s[left] != target:
                    others -= 1
                left += 1
            best = max(best, right - left + 1)
    return best

Jedno okno, które nigdy się nie zmniejsza

Intuicja

Utrzymuj 26 liczników dla okna oraz top, czyli najwyższy licznik. Gdy dodanie s[right] sprawia, że okno wymaga zbyt wielu zmian, usuń jedną literę z lewej strony: okno przesuwa się i zachowuje swoją długość, ponieważ tylko dłuższe okno może pobić rekord. W przeciwnym razie rośnie o jeden. Jego długość jest zawsze najlepsza z dotychczasowych, więc odpowiedzią jest n - left.

Gdy litera opuszcza okno, nie zmieniaj top, nawet jeśli jego wartość jest teraz większa od rzeczywistego licznika. Po przesunięciu długość wynosi dokładnie top + k, więc aby okno mogło urosnąć, jakaś litera musi wystąpić top + 1 razy — wtedy top również wzrasta. Nieaktualne top może jedynie spowodować przesunięcie okna, a przesunięcie nie może odebrać mu rekordu.

Dla BAAACAB przy k = 1 ciąg BAAAC wymaga 2 zmian, więc okno przesuwa się do AAAC. Następne A podnosi top do 4, a okno rośnie do AAACA o długości 5.

Algorytm

Zachowaj 26 liczników, left = 0 i top = 0.
Przesuwaj right po ciągu znaków: dodawaj s[right] do jego licznika i zwiększaj top, jeśli ten licznik jest teraz większy.
Jeśli right - left + 1 - top > k, usuń s[left] z liczników i przesuń left o jeden krok. Nigdy nie zmniejszaj top.
Zwróć długość końcowego okna, n - left.

def characterReplacement(s, k):
    count = [0] * 26  # letters inside the window s[left..right]
    left = 0
    top = 0  # the highest count any letter has reached in a window
    for right in range(len(s)):
        c = ord(s[right]) - ord('A')
        count[c] += 1
        top = max(top, count[c])
        # Needs more than k changes: slide the window instead of growing it.
        if right - left + 1 - top > k:
            count[ord(s[left]) - ord('A')] -= 1
            left += 1
    # The window only grew when a longer valid substring was found.
    return len(s) - left

Pułapki i przypadki brzegowe

Dodawanie k do najdłuższej serii. W AAAB przy k = 3 daje to 6, czyli więcej niż długość łańcucha. W BAAACAB przy k = 1 daje to 4, ale zmiana C łączy dwie serie w jedną o długości 5.
Liczenie zmian względem pierwszej litery okna zamiast względem najczęściej występującej litery. BAAA wymaga jednej zmiany, a nie trzech.
Zwracanie n - left z pętli, która zmniejsza okno za pomocą while i ponownie oblicza rzeczywiste maksimum. To okno staje się krótsze, więc zachowaj osobne best.
Obliczanie długości okna jako right - left. Oba końce należą do okna, więc dodaj jeden.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu zamiany znaków w celu uzyskania najdłuższego powtarzającego się ciągu znaków?

Rozwiązanie z jednym oknem działa w czasie O(n), gdzie n to długość s: right odwiedza każdą literę raz, a left przesuwa się co najwyżej raz na krok. Używa O(1) dodatkowej pamięci, 26 liczników i kilku liczb całkowitych.

Czym to się różni od problemu najdłuższego podciągu bez powtarzających się znaków?

W obu przypadkach przesuwamy dwa końce po ciągu, ale zasada określająca, kiedy okno jest poprawne, jest inna. Tam żaden znak nie może się powtarzać, więc okno zmniejsza się, aż powtórzenie zniknie. Tutaj długość minus liczność najczęstszego znaku musi być co najwyżej równa k, więc okno może przesuwać się ze stałą długością.

Czy ten problem można rozwiązać za pomocą wyszukiwania binarnego?

Tak. Jeśli osiągalny jest podciąg o długości L, to osiągalny jest też każdy krótszy podciąg w jego obrębie, więc można wyszukiwać binarnie wartość L. Dla każdej wartości L przesuwaj okno o stałej długości i sprawdzaj, czy istnieje pozycja wymagająca najwyżej k zmian. To rozwiązanie ma złożoność O(n log n), więc jest wolniejsze niż rozwiązanie z jednym oknem.

def characterReplacement(s, k):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

s = "BAAACAB"
k = 1

Oczekiwany wynik

Longest Repeating Character Replacement

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Sprawdź każdy podciąg znaków

Jedno przesuwne okno na każdą docelową literę

Jedno okno, które nigdy się nie zmniejsza

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania