Partition Labels

Między sąsiednimi literami jest n-1 przerw. Cięcie w przerwie jest dozwolone tylko wtedy, gdy żadna litera nie występuje po obu jej stronach, ponieważ litera rozdzielona cięciem znalazłaby się w dwóch częściach. Wykonanie wszystkich dozwolonych cięć daje najwięcej części. Weźmy fragment między dwoma sąsiednimi dozwolonymi cięciami: żadna z jego liter nie występuje na lewo od lewego cięcia ani na prawo od prawego cięcia, więc wszystkie ich wystąpienia znajdują się wewnątrz fragmentu i jest on prawidłową częścią. Każda prawidłowa odpowiedź może zaś zawierać cięcia tylko w dozwolonych przerwach, więc żadna odpowiedź nie ma więcej części.

Sprawdź więc każdą przerwę: zbierz litery po jej lewej i prawej stronie i wykonaj cięcie, jeśli zbiory nie mają wspólnych elementów. W abacdcefe po aba po lewej stronie przerwy są a i b, a po prawej c, d, e i f. Nie ma wspólnych liter, więc wykonujesz cięcie. Po ab po obu stronach przerwy występuje a, więc nie wykonujesz cięcia.

Każde sprawdzenie wymaga odczytania całego ciągu, a przerw jest n-1, więc trzeba odczytać około n² liter. Przy 50 000 liter oznacza to 2.5 × 10^9 odczytów, zdecydowanie za dużo, by największe testy działały wystarczająco szybko.

Potraktuj każdą literę jako przedział od jej pierwszej do ostatniej pozycji. Część zawierająca daną literę musi obejmować cały ten przedział. Zatem dwie litery, których przedziały się nakładają, muszą znaleźć się w tej samej części, a nakładanie się rozprzestrzenia: jeśli przedział a nakłada się na b, a przedział b na c, wszystkie trzy znajdą się w jednej części.

To problem scalania przedziałów. W jednym przebiegu zanotuj pierwszą i ostatnią pozycję każdej litery. Następnie weź przedziały w kolejności ich początków i scal te, które się nakładają. Każdy scalony blok stanowi jedną część, a przerwy między blokami to dokładnie dozwolone miejsca podziału. Otrzymasz przedziały w kolejności początków bez sortowania: przejdź ponownie po ciągu i pobierz przedział litery, gdy znajdziesz się na jej pierwszej pozycji.

W ciągu codingisfun przedziały w kolejności to c [0, 0], o [1, 1], d [2, 2], i [3, 6], n [4, 10], g [5, 5], s [7, 7], f [8, 8] i u [9, 9]. Pierwsze trzy tworzą osobne części. Począwszy od i, każdy przedział zaczyna się na pozycji 10 lub wcześniej, a na tej pozycji kończy się przedział n, więc łączą się w [3, 10], czyli część złożoną z 8 liter.

Ciąg zawiera najwyżej 26 różnych liter, więc przedziałów jest najwyżej 26, a tablice pierwszych i ostatnich pozycji mają stały rozmiar.

Pierwsze pozycje wcale nie są potrzebne. Czytaj ciąg znaków od lewej do prawej i przechowuj w end najbardziej odległą ostatnią pozycję dowolnej litery w bieżącej części. Gdy odczytasz literę na pozycji i, jej ostatnie wystąpienie również musi znajdować się w tej części, więc zwiększ end do last[s[i]], jeśli ta wartość jest większa.

Gdy i osiągnie end, ostatnie wystąpienie każdej odczytanej w tej części litery znajduje się na pozycji i lub wcześniej. Żadna litera nie przekracza przerwy za i, więc można tam zrobić cięcie. Zamknij część o długości end-start+1 i rozpocznij następną od i+1.

Dlaczego cięcie przy pierwszej okazji jest właściwym wyborem zachłannym? Zanim i osiągnie end, jakaś litera z tej części nadal ma wystąpienie dalej w ciągu, więc nie można wykonać wcześniejszego cięcia. Przejście nie pomija też żadnej dozwolonej przerwy: jeśli żadna litera nie przekracza przerwy za i, ostatnie wystąpienie każdej litery z tej części znajduje się na pozycji i lub wcześniej, więc end jest wtedy równe i. Przejście wykonuje cięcia dokładnie w dozwolonych miejscach, co daje najwięcej części.

W ciągu abacdcefe ostatnie pozycje to: a — 2, b — 1, c — 5, d — 4, e — 8 i f — 7. Odczytanie a ustawia end na 2, b pozostawia tę wartość bez zmian, a na i = 2 część zostaje zamknięta i ma długość 3. Litera c ustawia end na 5 i część zostaje zamknięta na pozycji 5 — ponownie ma długość 3. Część z e zostaje zamknięta na pozycji 8.