Længste palindromiske delsekvens og delstreng

En palindromisk delsekvens er en delsekvens (elementerne behøver ikke at være sammenhængende), der læses ens forfra og bagfra. En palindromisk delstreng kræver sammenhængende tegn. For 'bbbab' er den længste palindromiske delsekvens 'bbbb' (længde 4), mens den længste palindromiske delstreng er 'bbb' (længde 3). De to problemer kræver forskellige teknikker trods deres lignende navne.

Definér dp[i][j] som længden af den længste palindromiske delsekvens i s[i..j]. Rekurrensformlen er: Hvis s[i] == s[j], så er dp[i][j] = dp[i+1][j-1] + 2 (de to ens tegn udvider det indre palindrom). Ellers er dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (spring det venstre eller højre tegn over). Basistilfælde: dp[i][i] = 1 for alle enkelte tegn.

Vi udfylder LPS-tabellen i stigende intervallængde, efter samme mønster som generel interval-DP. For hvert interval [i, j] med længde 2 eller mere kontrollerer vi, om de to grænsetegn er ens, og anvender rekurrensformlen. Det endelige svar er dp[0][n-1], LPS for hele strengen.

Et elegant alternativ: LPS for strengen s er lig med LCS for s og dens omvendte streng s[::-1]. Det skyldes, at enhver palindromisk delsekvens i s er en fælles delsekvens for s og dens omvendte streng. Denne omskrivning giver dig mulighed for at genbruge din LCS-implementering direkte. Den omvendte version af 'bbbab' er 'babbb', og deres LCS er 4.

Den længste palindromiske delstreng kræver sammenhængende tegn. En brute force-tilgang kontrollerer alle O(n²) delstrenge og verificerer hver af dem i O(n)-tid — O(n³) i alt. Der findes to hurtigere tilgange: interval-DP i O(n²)-tid og med O(n²)-pladsforbrug samt udvidelse omkring centrum i O(n²)-tid, men med O(1)-pladsforbrug. Til interviews foretrækkes udvidelse omkring centrum, fordi den har en mindre konstant faktor og renere kode.

Definér dp[i][j] = True, hvis s[i..j] er et palindrom. Rekurrensformel: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. Basistilfælde: dp[i][i] = True og dp[i][i+1] = (s[i] == s[i+1]). Hold styr på det længste fundne palindrom. Udfyld tabellen i stigende længderækkefølge. Det kører i O(n²)-tid og bruger O(n²)-plads.

Tilgangen med udvidelse omkring centrum prøver hvert tegn (samt hvert par af tilstødende tegn) som et muligt palindromcentrum og udvider udad, så længe begge sider matcher. Der er 2n-1 mulige centre (n for ulige længder og n-1 for lige længder). Hver udvidelse tager højst O(n)-tid, hvilket giver O(n²) i alt med O(1)-pladsforbrug — optimalt i de fleste interviewsituationer.

Interval-DP for LPS bruger O(n²)-plads. Når du kun har brug for længden (og ikke den faktiske delsekvens), kan du reducere pladsforbruget ved at bemærke, at dp[i][j] kun afhænger af dp[i+1][j-1], dp[i+1][j] og dp[i][j-1]. Ved at genbruge rækker og gemme én diagonalværdi kan du opnå O(n)-plads — implementeringen bliver dog mere kompleks, og det er sjældent nødvendigt i interviews.

Hvis du vil genskabe den faktiske palindromiske delsekvens, skal du spore tilbage gennem DP-tabellen. Start ved (0, n-1). Hvis s[i] == s[j], skal du føje tegnet til begge ender af dit resultat og gå til (i+1, j-1). Ellers skal du gå til den af (i+1, j) og (i, j-1), der har den største værdi. Denne grådige tilbagesporing genskaber entydigt én optimal palindromisk delsekvens.

Både LPS via interval-DP og LCS kører i O(n²)-tid og bruger O(n²)-plads. Udvidelse omkring centrum for den længste palindromiske delstreng bruger O(n²)-tid, men kun O(1)-plads. Manachers algoritme løser delstrengsproblemet i O(n)-tid og med O(n)-plads, men den er så kompleks, at interviewere sjældent forventer den. I de fleste interviewsituationer er udvidelse omkring centrum den forventede optimale løsning på delstrengsvarianten.

Vær opmærksom på disse faldgruber: (1) at forveksle subsekvens med delstreng — det er forskellige problemer med forskellige løsninger; (2) basistilfældet i interval-DP'en for intervaller af længde 2 kræver særskilt håndtering, eftersom dp[i+1][j-1] ville være dp[i+1][i] (et tomt interval); (3) ved udvidelse omkring centrum skal du initialisere max_len = 1 (hvert enkelt tegn er et palindrom); og (4) når du udtrækker resultatet, skal du beregne start = i - (best-1)//2 for korrekt at finde startindekset ud fra centrum.

I denne lektion lærte du: LPS bruger interval-DP med rekurrensen dp[i][j] = dp[i+1][j-1]+2, når tegnene matcher, den længste palindromiske delstreng løses bedst med udvidelse omkring centrum i O(n²)-tid og med O(1)-pladsforbrug, og LPS er lig med LCS for strengen og dens omvendte streng. Næste emne er palindromopdeling II, hvor en palindromtabel kombineres med 1D-DP for at finde det mindste antal snit.