how to find longest palindromic subsequence?

Question

Here is the problem (6.7 ch6 ) from Algorithms book (by Vazirani) that slightly differs from the classical problem that finding longest palindrome. How can I solve this problem ?

A subsequence is palindromic if it is the same whether read left to right or right to left. For instance, the sequence

A,C,G,T,G,T,C,A,A,A,A,T,C,G

has many palindromic subsequences, including A,C,G,C,A and A,A,A,A (on the other hand, the subsequence A,C,T is not palindromic). Devise an algorithm that takes a sequence x[1 ...n] and returns the (length of the) longest palindromic subsequence. Its running time should be O(n^2)

Solution 1

This can be solved in O(n^2) using dynamic programming. Basically, the problem is about building the longest palindromic subsequence in x[i...j] using the longest subsequence for x[i+1...j], x[i,...j-1] and x[i+1,...,j-1] (if first and last letters are the same).

Firstly, the empty string and a single character string is trivially a palindrome. Notice that for a substring x[i,...,j], if x[i]==x[j], we can say that the length of the longest palindrome is the longest palindrome over x[i+1,...,j-1]+2. If they don't match, the longest palindrome is the maximum of that of x[i+1,...,j] and y[i,...,j-1].

This gives us the function:

longest(i,j)= j-i+1 if j-i<=0,
              2+longest(i+1,j-1) if x[i]==x[j]
              max(longest(i+1,j),longest(i,j-1)) otherwise

You can simply implement a memoized version of that function, or code a table of longest[i][j] bottom up.

This gives you only the length of the longest subsequence, not the actual subsequence itself. But it can easily be extended to do that as well.

---

Solution 2

This problem can also be done as a variation of a very common problem called the LCS(Longest Common sub sequence) problem. Let the input string be represented by a character array s1[0...n-1].

1) Reverse the given sequence and store the reverse in another array say s2[0..n-1] which in essence is s1[n-1....0]

2) LCS of the given sequence s1 and reverse sequence s2 will be the longest palindromic sequence.

This solution is also a O(n^2) solution.

Solution 3

It makes me a little confused that the difference between substring and subsequence.(See Ex6.8 and 6.11) According to our comprehension of subsequence, the giving example doesn't have the palindromic subsequence ACGCA. Here's my pseudo code, I'm not quite sure about the initialization ><

for i = 1 to n do
    for j = 1 to i-1 do
        L(i,j) = 0
for i = 1 to n do
    L(i,i) = 1
for i = n-1 to 1 do    //pay attention to the order when filling the table
    for j = i+1 to n do
        if x[i] = x[j] then
           L(i,j) = 2 + L(i+1, j-1)
        else do
           L(i,j) = max{L(i+1, j), L(i, j-1)}
return max L(i,j)

preparing for the algorithm final...