Longest Repeating Character Replacement

Popraw jeden fragment. Na jaką literę należy go zmienić? Na tę, która już występuje najczęściej, ponieważ każda inna litera musi się zmienić. Zatem fragment o długości len, w którym najczęściej występująca litera pojawia się top razy, wymaga len - top zmian i jest osiągalny, gdy ta wartość nie przekracza k.

Wypróbuj każdy fragment. Dla każdego początku zwiększaj koniec o jedną literę i zliczaj wystąpienia każdej litery, zwiększając przy tym top. Każdy kolejny fragment wymaga wtedy jednej aktualizacji zamiast ponownego zliczania od początku. Sprawdzane są wszystkie fragmenty, więc nie da się przeoczyć najdłuższego osiągalnego.

To rozwiązanie jest powolne, ponieważ ciąg o długości n ma około n²/2 fragmentów. Dla n = 5 × 10^4 oznacza to 1.25 × 10^9 sprawdzeń, czyli znacznie więcej, niż pozwala limit czasu.

Odwróć pytanie i najpierw wybierz literę. Jeśli końcowy ciąg składa się wyłącznie z A, pytanie brzmi: jaki jest najdłuższy podciąg zawierający co najwyżej k liter, które nie są A? To klasyczne okno przesuwne.

Przesuwaj right po ciągu i zliczaj litery wewnątrz okna, które nie są literą docelową. Gdy ich liczba przekroczy k, przesuwaj left do przodu, aż znów będzie ich k. Powiększanie okna może jedynie dodawać litery do zmiany, więc okno, którego zmiana wymaga zbyt wiele, nadal będzie wymagać zbyt wiele po powiększeniu, a left nigdy nie musi się cofać. Dla każdego right zachowywane okno jest najdłuższym poprawnym oknem kończącym się w tym miejscu.

Wykonaj to dla wszystkich 26 liter i zachowaj najlepszą długość. Każde przejście zajmuje O(n), więc łącznie jest to 26 przejść, czyli około 1.3 × 10^6 kroków dla n = 5 × 10^4. To rozwiązanie liniowe, ale odczytuje ciąg 26 razy i działa tylko dlatego, że alfabet jest mały.

Obsłuż każdą literę w jednym oknie. Zliczaj wystąpienia każdej z 26 liter w tym oknie oraz top, czyli największą liczbę wystąpień. Okno wymaga length - top zmian, więc jest poprawne, jeśli ta wartość nie przekracza k.

Pierwszy fakt: okno nigdy nie musi się zmniejszać. Zależy ci tylko na pobiciu najlepszego dotąd znalezionego wyniku, więc gdy dodanie s[right] sprawia, że okno wymaga zbyt wielu zmian, usuń jedną literę z lewej strony. Okno przesuwa się o jeden krok i zachowuje swoją długość. Gdy okno nie wymaga zbyt wielu zmian, zwiększa się o jeden. Jego długość jest więc zawsze równa najlepszej dotąd znalezionej długości, a na końcu odpowiedzią jest n - left.

Drugi fakt: wartość top nigdy nie musi maleć. Gdy litera opuszcza okno z lewej strony, nie zmieniasz top, więc może być większe niż rzeczywista liczba wystąpień w oknie. To bezpieczne. Po przesunięciu długość okna wynosi dokładnie top + k, więc jego zwiększenie wymaga litery, która występuje w oknie top + 1 razy, i wtedy top rośnie razem z nią. Nieaktualne top może spowodować przesunięcie okna, ale nigdy błędne jego zwiększenie, a przesunięcie niczego nie tracimy, bo rekord może pobić tylko dłuższe okno.

Dla BAAACAB przy k = 1 okno rośnie do BAAA, a następnie BAAAC wymaga 2 zmian, więc przesuwa się do AAAC. Dodanie kolejnego A zwiększa top do 4, a okno rośnie do AAACA o długości 5. Ostatnie B powoduje jeszcze jedno przesunięcie, więc odpowiedzią jest 5.