Longest Valid Parentheses

Czytaj podciąg od lewej do prawej, śledząc bilans, który zwiększa się o 1 dla ( i zmniejsza o 1 dla ). Podciąg jest poprawny dokładnie wtedy, gdy bilans nigdy nie spada poniżej 0 i na końcu wynosi 0. Wartość poniżej 0 oznacza, że pojawił się znak ), który nie miał żadnego otwartego nawiasu do zamknięcia.

Ustal więc początek i przechodź w prawo, aktualizując bilans po jednym znaku. Za każdym razem, gdy bilans wraca do 0, fragment od początku do tego miejsca jest poprawny, więc zapisujesz jego długość. Gdy tylko bilans spadnie poniżej 0, zatrzymaj się: ten znak ) pozostanie niedopasowany w każdym dłuższym fragmencie zaczynającym się w tym miejscu. Każdy poprawny podciąg ma jakiś początek, a dla każdego z nich sprawdzasz wszystkie możliwe końce, więc niczego nie pomijasz.

Problemem jest koszt. W ciągu złożonym z 59998 znaków (, po których następuje (), bilans nigdy nie spada poniżej 0, więc dla każdego początku przechodzisz do końca: około n²/2 = 1.8 × 10^9 kroków dla n = 6 × 10^4. Duże testy są skonstruowane właśnie w ten sposób. (Sprawdzanie każdego podciągu od początku zamiast jego rozbudowy byłoby jeszcze wolniejsze: O(n³).)

Dopasowywanie nawiasów za pomocą stosu jest dobrze znane: dodawaj każdy ( na stos, a przy każdym ) zdejmuj jeden element. Tutaj potrzebujesz także długości, więc dodawaj indeksy i zachowaj na dole stosu jeden dodatkowy indeks: bazę, czyli pozycję tuż przed ciągiem, w którym się znajdujesz. Na początku nic nie zostało odczytane, więc baza wynosi -1.

Przy ( dodaj jego indeks na stos. Przy ) zdejmij element ze stosu. Mogą się zdarzyć dwie rzeczy. Jeśli stos jest teraz pusty, zdjęty został indeks bazy, więc ten ) nie miał pasującego nawiasu otwierającego. Żaden poprawnie sformowany podciąg nie może go zawierać i staje się on nową bazą: dodaj jego indeks na stos. W przeciwnym razie indeks pozostały na wierzchu to ostatni znak przed ciągiem kończącym się na i: albo wciąż niedomknięty (, albo baza. Wszystko po nim aż do i jest dopasowane, a ciąg nie może sięgać dalej w lewo, więc jego długość wynosi i - top.

Oto ())((()):

• i = 0, (: dodaj 0 na stos. Stos [-1, 0].
• i = 1, ): zdejmij 0. Na wierzchu jest -1, więc ciąg ma długość 1 - (-1) = 2.
• i = 2, ): zdejmij -1 i stos jest pusty. Ten ) nie ma pary, więc dodaj 2 jako nową bazę. Stos [2].
• i = 3, 4, 5, trzy (: dodaj je na stos. Stos [2, 3, 4, 5].
• i = 6, ): zdejmij 5. Na wierzchu jest 4, więc ciąg ma długość 6 - 4 = 2.
• i = 7, ): zdejmij 4. Na wierzchu jest 3, więc ciąg ma długość 7 - 3 = 4, czyli jest to odpowiedź.

Baza sprawia, że stykające się fragmenty łączą się. Dla ()(()) pierwsza para ma długość 1 - (-1) = 2, a ostatni ) zdejmuje indeks 2 i ponownie znajduje -1 na wierzchu, więc oblicza 5 - (-1) = 6. Liczenie od pasującego ( dałoby zamiast tego 4 i pominęłoby poprzedzające (). Każdy indeks jest dodawany na stos i zdejmowany z niego najwyżej raz, więc przejście ma złożoność O(n), a stos może przechowywać do n+1 indeksów.

Stos mówi tylko, gdzie zaczęła się bieżąca seria. Dwa liczniki też mogą to ustalić. Przejdź od lewej do prawej, zliczając opens i closes od ostatniego resetu. Gdy są równe, wszystko od resetu jest poprawnie sformowane, a jego długość wynosi 2 × closes. Gdy closes wysunie się na prowadzenie, nawias ) nie ma pary — w tej samej chwili stos stracił swoją podstawę — więc zresetuj oba liczniki do 0.

Jedno przejście nie wystarczy. Nawias (, który nigdy się nie zamyka, sprawia, że opens na zawsze wyprzedza closes, a liczniki już się nie zrównają. Dla (() przejście w lewo kończy się wynikiem 2 otwarcia i 1 zamknięcie i niczego nie zgłasza, choć () znajduje się tuż obok. Przejdź więc drugi raz, od prawej do lewej, zamieniając role: resetuj, gdy opens wysunie się na prowadzenie. Czytając od tyłu, dla (() najpierw napotykasz nawias zamykający, potem otwierający (liczniki są równe: długość 2), a następnie otwierający, który powoduje reset. Odpowiedzią jest większy wynik z tych dwóch przejść.

Dlaczego dwa przejścia znajdują każdą serię: najdłuższa seria jest ograniczona znakami, których nigdy nie można dopasować, albo końcami ciągu. Jeśli jej lewą granicą jest zbędny nawias ) lub początek ciągu, lewe przejście resetuje liczniki dokładnie tam, gdzie zaczyna się seria, i zauważa ich zrównanie w miejscu, gdzie się kończy. Jeśli jej lewą granicą jest zbędny nawias (, jej prawa granica nie może być nawiasem ), bo ten nawias ) zamknąłby zbędny nawias (, a seria byłaby dłuższa. Zatem prawą granicą jest zbędny nawias ( lub koniec ciągu, a prawe przejście znajduje serię w ten sam sposób. Każde przejście odczytuje ciąg raz, używając dwóch liczb całkowitych, więc czas działania wynosi O(n), a dodatkowa pamięć O(1).