Longest palindromic subsequence

Question

Given a string, find the length of its longest palindromic subsequence: a sequence you get by deleting zero or more characters (keeping order) that reads the same both ways. Unlike a substring, it need not be contiguous.

"bbbab"  -> 4     # "bbbb"
"cbbd"   -> 2     # "bb"
"abc"    -> 1

Return the length in $O(n^2)$ time. The expand-around-center trick does not apply here; think in terms of the ends of a range.

Accepted Answer

Because the characters can be non-contiguous, there is no single center to grow from. Instead reason about the two ends of a range s[i..j]. Let dp[i][j] be the longest palindromic subsequence within that range. - If s[i] == s[j], those two characters can wrap around the best palindrome of the interior: dp[i][j] = dp[i+1][j-1] + 2. - If they differ, at least one end cannot both be used, so drop one: dp[i][j] = max(dp[i+1][j], dp[i][j-1]). - A single character is a palindrome of length 1: dp[i][i] = 1. Fill the table over increasing range length (equivalently, i descending, j ascending). Tracin…

Longest palindromic subsequence

Your answer

More Coding questions