Longest palindromic subsequence and substring

The idea: answer the question for every interval s[i..j]

A palindrome reads the same forwards and backwards, like racecar. Two classic questions ask for the longest palindrome inside a string. A subsequence may skip letters; a substring must be one unbroken run. Both are solved by interval dynamic programming: a table cell (i, j) holds the answer for the letters s[i..j], and it is computed from shorter intervals only.

The table is an upper triangle

For a string of length n there is a cell for every pair i ≤ j: n(n + 1)/2 cells, the upper triangle of an n × n grid. Row i is where the interval starts, column j where it ends. While a cell is being filled, the page lights up the letters s[i..j] in the string above the table and colours the two ends green when they are equal, red when they differ.

Subsequence: the recurrence

Let dp[i][j] be the length of the longest palindromic subsequence of s[i..j]. One letter is a palindrome, so dp[i][i] = 1. For a longer interval, look only at its two ends:

• Ends equal, s[i] = s[j]: put them around the best palindrome of the inside, dp[i][j] = dp[i+1][j−1] + 2. For two letters the inside is empty and counts 0.
• Ends differ: they cannot both be the outer letters, so one of them is not used. dp[i][j] = max(dp[i+1][j], dp[i][j−1]): drop the left end or the right end, keep the better.

Filling diagonal by diagonal

Every cell reads intervals that are one or two letters shorter. So the table is filled by length: first the diagonal (length 1), then all intervals of two letters, then three, up to dp[0][n−1], the answer in the top right corner. Each Step of the animation fills one cell. Filling row by row from the top would be wrong: dp[0][2] needs dp[1][1] and dp[1][2] from the next row. This is the same order as the matrix chain table. (Demo: BBABCBCAB, longest subsequence)

Trace back: spell the palindrome

The table gives only the length. To get the letters, start at (0, n−1) and repeat: if the ends are equal, take both and move inside to (i+1, j−1); if they differ, move to the neighbour the value came from, down to (i+1, j) or left to (i, j−1) (ties go down); when i = j, that letter is the middle. The page colours each cell on the path and each letter taken. For BBABCBCAB this gives BACBCAB, length 7; BABCBAB is another answer of the same length, found with another tie rule. For character it gives carac, length 5. (Demo: character, longest subsequence)

A neat fact: the longest palindromic subsequence of s is the longest common subsequence of s and its reverse.

Substring: a true/false table

For substrings the letters must be consecutive, so there is no "drop one end". P[i][j] is T when s[i..j] is a palindrome: P[i][i] = T, and P[i][j] = T exactly when s[i] = s[j] and the inside s[i+1..j−1] is a palindrome (or empty, for two letters). The table fills in the same diagonal order, and the answer is the longest T cell. For babad both bab and aba have length 3; the page keeps the first one found, bab. For cbbd it is bb. (Demo: babad, longest substring, Demo: cbbd, longest substring)

string	longest subsequence	longest substring
BBABCBCAB	BACBCAB (7)	BAB (3)
character	carac (5)	ara (3)
babad	aba (3)	bab (3)
cbbd	bb (2)	bb (2)

(Demo: BBABCBCAB as a substring shows how much shorter the unbroken answer can be.)

Faster for substrings: Manacher's algorithm

Both tables take Θ(n²) time and space. For the substring problem there are faster ways. Expand around the centre tries each of the 2n − 1 centres and grows outwards while the letters match: still O(n²) time, but O(1) space. Manacher's algorithm reuses the mirror image of a palindrome it has already found, so it never re-checks a letter inside the rightmost palindrome, and finds the longest palindromic substring in O(n) time. See Manacher's Algorithm. The subsequence problem has no such shortcut in general; the quadratic table is the usual answer.

Running time and space

There are n(n + 1)/2 cells and each takes O(1) work: Θ(n²) time and space. Trying every subsequence instead would mean 2ⁿ candidates; trying every substring and checking it, O(n³). The subsequence table can be kept in O(n) space with one row per length when only the length is needed, but then the trace back is lost.

See also Longest Common Subsequence, Matrix Chain Multiplication for another interval DP, and Edit Distance.

What the page leaves out

Strings are capped at 10 letters so the table fits on the canvas, and letters are compared case-sensitively. The page shows one longest answer, not all of them, and leaves out the memoized top-down version, the space-saving rolling rows, the minimum insertions to make a palindrome (n − dp[0][n−1]), and the details of Manacher's algorithm.

References

Longest palindromic subsequence (Wikipedia)

Longest palindromic substring and Manacher's algorithm (Wikipedia)

Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, problem 14-2 Longest palindrome subsequence