Langste palindromische subsequence en substring

Een palindromische deelrij is een deelrij (waarvan de elementen niet per se aaneengesloten zijn) die van voren naar achteren en omgekeerd hetzelfde leest. Een palindromische deelstring vereist aaneengesloten tekens. Voor 'bbbab' is de langste palindromische deelrij 'bbbb' (lengte 4), terwijl de langste palindromische deelstring 'bbb' is (lengte 3). Deze twee problemen vereisen verschillende technieken, ondanks hun vergelijkbare namen.

Definieer dp[i][j] als de lengte van de langste palindromische deelrij in s[i..j]. De recursieformule is: als s[i] == s[j], dan is dp[i][j] = dp[i+1][j-1] + 2 (de twee gelijke tekens breiden het binnenste palindroom uit). Anders is dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (sla het teken links of rechts over). Basisgeval: dp[i][i] = 1 voor elk afzonderlijk teken.

We vullen de LPS-tabel in volgorde van oplopende intervallengte in, volgens hetzelfde patroon als algemene interval-DP. Voor elk interval [i, j] met lengte 2 of meer controleren we of de twee grenswaarden gelijk zijn en passen we de recursieformule toe. Het uiteindelijke antwoord is dp[0][n-1], de LPS van de volledige tekenreeks.

Een elegant alternatief: de LPS van tekenreeks s is gelijk aan de LCS van s en de omgekeerde tekenreeks s[::-1]. Dat komt doordat elke palindromische deelrij van s een gemeenschappelijke deelrij is van s en de omgekeerde tekenreeks. Dankzij deze omzetting kun je je LCS-code rechtstreeks hergebruiken. De omgekeerde versie van 'bbbab' is 'babbb' en hun LCS heeft lengte 4.

De langste palindromische deelstring vereist aaneengesloten tekens. Een uitputtende aanpak controleert alle O(n²) deelstrings en verifieert elke deelstring in O(n) tijd — in totaal O(n³). Er bestaan twee snellere aanpakken: interval-DP in O(n²) tijd en ruimte en uitbreiden rond het midden in O(n²) tijd maar O(1) ruimte. Voor sollicitatiegesprekken heeft uitbreiden rond het midden de voorkeur, omdat de constante factor kleiner is en de code overzichtelijker.

Definieer dp[i][j] = True als s[i..j] een palindroom is. Recursieformule: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. Basisgevallen: dp[i][i] = True en dp[i][i+1] = (s[i] == s[i+1]). Houd de langste gevonden palindroom bij. Vul de tabel in volgorde van oplopende lengte in. Dit werkt in O(n²) tijd en O(n²) ruimte.

De aanpak uitbreiden rond het midden probeert elk teken en elk paar aangrenzende tekens als mogelijk palindroommidden en breidt naar buiten uit zolang beide zijden overeenkomen. Er zijn 2n-1 mogelijke middelpunten (n voor palindromen met oneven lengte en n-1 voor palindromen met even lengte). Elke uitbreiding kost hoogstens O(n) tijd, wat in totaal O(n²) oplevert met O(1) ruimte — optimaal voor de meeste sollicitatiegesprekken.

De interval-DP voor LPS gebruikt O(n²) ruimte. Wanneer je alleen de lengte nodig hebt en niet de daadwerkelijke deelrij, kun je de ruimte beperken door te zien dat dp[i][j] alleen afhankelijk is van dp[i+1][j-1], dp[i+1][j] en dp[i][j-1]. Door rijen opnieuw te gebruiken en één diagonaalwaarde te bewaren, kun je O(n) ruimte bereiken — hoewel de implementatie complexer is en zelden nodig is tijdens sollicitatiegesprekken.

Om de daadwerkelijke palindromische deelrij te reconstrueren, loop je terug door de DP-tabel. Begin bij (0, n-1). Als s[i] == s[j], voeg je dat teken aan beide uiteinden van je resultaat toe en ga je naar (i+1, j-1). Ga anders naar (i+1, j) of (i, j-1), afhankelijk van welke de grotere waarde heeft. Met deze hebzuchtige terugloop reconstrueer je op unieke wijze één optimale palindromische deelrij.

Zowel LPS via interval-DP als LCS werken in O(n²) tijd en O(n²) ruimte. Uitbreiden rond het midden voor de langste palindromische deelstring kost O(n²) tijd maar slechts O(1) ruimte. Het algoritme van Manacher lost het deelstringprobleem op in O(n) tijd en ruimte, maar is zo complex dat interviewers het zelden verwachten. In de meeste contexten van sollicitatiegesprekken is uitbreiden rond het midden de verwachte optimale oplossing voor de variant met deelstrings.

Let op deze valkuilen: (1) een niet-aaneengesloten deelreeks verwarren met een aaneengesloten deelreeks — het zijn verschillende problemen met verschillende oplossingen; (2) voor het basisgeval van interval-dp met intervallen van lengte 2 is speciale afhandeling nodig, omdat dp[i+1][j-1] gelijk zou zijn aan dp[i+1][i] (leeg interval); (3) initialiseer bij uitbreiden rond het midden max_len = 1 (elk afzonderlijk teken is een palindroom); en (4) bereken bij het ophalen van het resultaat start = i - (best-1)//2 om de startindex correct vanuit het midden te bepalen.

In deze les heb je geleerd: LPS gebruikt interval-dp met de recurrentie dp[i][j] = dp[i+1][j-1]+2 wanneer de tekens overeenkomen, de langste palindromische deeltekenreeks los je het best op met uitbreiden rond het midden in O(n²) tijd en O(1) ruimte, en LPS is gelijk aan LCS van de tekenreeks en het omgekeerde daarvan. Hierna behandelen we palindroompartitionering II, waarin een palindroomtabel wordt gecombineerd met 1D-dp voor het minimale aantal knippen.