8 Dec 2011
Given a string s, find the longest palindromic subsequence
A subsequence of string is the string with some characters removed. For example, aaa is a subsequence of bcabcabca.
First of all, let's try a brute-force solution.
A really really stupid brute-force solution is to generate all possible subsequences. There are 2^n-1 subsequences, btw.
Let's try some observation first. Consider
x 1 c x 1 x 1, where c is the center.
We have to match the first 1 with the second 1. It does not make sense to match with the third 1.
Another observation is:
x x 1 x x x x 1 x x x 1
In this case, it is not decisive. Any pair of 1s can be a part of the longest palindrome.
I'm pretty convinced that we have to fix the center. But how can we iterate all possible palindromes around a center?
I cannot come up with a better brute-force solution. Let's just move on to a dynamic-programming approach
I'm pretty damn sharp with the dynamic programming :P
The problem can be decomposed. Let's say between a[i] and a[j] the longest palindrome is of length k. If a[i-1] and a[j+1] are equal, then the longest palindrome between a[i-1] and a[j+1] is k+2.
That sounds reasonable. The complete solution is:
d[i,j] is the length of the longest palindrome between a[i] and a[j] d[i,j] = d[i+1, j-1]+2 if a[i] == a[j], otherwise d[i+1,j-1] d[i,i] = 1 d[i,i+1] = 2 if a[i] == a[i+1], otherwise 0
That is O(n2) in time and O(n2) in space. Can we improve it?
After googling for a while, I don't think there is a better solution. However, as d[i,j] only requires d[i+1,j-1], we can improve to O(n) in space.