Longest Palindromic Subsequence

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

Dynamic programming solution

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.

Give it a kudos