How to find the longest palindromic subsequence (not its length)

Question

I want to find out the longest palindromic subsequence in a string. Everywhere I find the algorithm to find out the length of the subsequence, with the statement that the algo can be extended to return the subsequence as well, but nowhere have I found how. Can anybody explain how can I get the sequence as well?

Answer 1

Since you mentioned the link Longest Palindromic Subsequence in geeksforgeeks, I modified the solution to output the result. I think we need one auxiliary two-dimensions array to stored how the palindromic subsequence comes from, so we can get the result through the auxiliary array at last. You can see the logic in the below code:

#include<iostream>
#include<cstring>

using namespace std;

// A utility function to get max of two integers
int max (int x, int y) { return (x > y)? x : y; }

// Returns the length of the longest palindromic subsequence in seq
int lps(char *str,char *result)
{
   int n = strlen(str);
   int i, j, cl;
   int L[n][n];  // Create a table to store results of subproblems

   int Way[n][n];// Store how the palindrome come from.


   // Strings of length 1 are palindrome of lentgh 1
   for (i = 0; i < n; i++)
   {
       L[i][i] = 1;
       Way[i][i]=0;
   }


    // Build the table. Note that the lower diagonal values of table are
    // useless and not filled in the process. The values are filled in a
    // manner similar to Matrix Chain Multiplication DP solution (See
    // http://www.geeksforgeeks.org/archives/15553). cl is length of
    // substring
    for (cl=2; cl<=n; cl++)
    {
        for (i=0; i<n-cl+1; i++)
        {
            j = i+cl-1;
            if (str[i] == str[j] && cl == 2)
            {
                   L[i][j] = 2;
                   Way[i][j]=0;     
            }

            else if (str[i] == str[j])
            {
                  L[i][j] = L[i+1][j-1] + 2;
                  Way[i][j]=0;
            }

            else
            {
                if(L[i][j-1]>L[i+1][j])
                {
                   L[i][j]=L[i][j-1];
                   Way[i][j]=1;                    
                }
                else
                {
                    L[i][j]=L[i+1][j];
                    Way[i][j]=2;  
                }

            }

        }
    }

    int index=0;
    int s=0,e=n-1;

    while(s<=e)
    {
         if(Way[s][e]==0)
         {
             result[index++]=str[s];
             s+=1;
             e-=1;

         }
         else if(Way[s][e]==1)e-=1;
         else if(Way[s][e]==2)s+=1;     
    }

    int endIndex=(L[0][n-1]%2)?index-1:index;

    for(int k=0;k<endIndex;++k)result[L[0][n-1]-1-k]=result[k];

    result[index+endIndex]='\0';


    return L[0][n-1];
}

/* Driver program to test above functions */
int main()
{
    char seq[] = "GEEKSFORGEEKS";
    char result[20];
    cout<<"The lnegth of the LPS is "<<lps(seq,result)<<":"<<endl;
    cout<<result<<endl;
    getchar();
    return 0;
}

Hope it helps!

Below is the explanation:

Let X[0..n-1] be the input sequence of length n and L(0, n-1) be the length of the longest palindromic sub-sequence of X[0..n-1].

There are 5 cases in total.

1)Every single character is a palindrome of length 1. L(i, i) = 1 for all indexes i in given sequence.

2)There are only 2 characters and both are same. L(i, j) = 2.

3)There are more than two characters, and first and last characters are the same L(i, j) = L(i + 1, j - 1) + 2

4)First and last characters are not the same and L(i + 1, j)< L(i, j - 1). L(i, j) = L(i, j - 1).

5)First and last characters are not the same and L(i + 1, j)>=L(i, j - 1). L(i, j) = L(i + 1, j).

We can observed that only in case 1,2 and 3, the character X[i] is included in the final result. We used a two-dimension auxiliary array to represent how the palindromic sub-sequence comes from. value 0 for case 1,2,3; value 1 for case 4; value 2 for case 5.

With the auxiliary array Way. We can get the result as below:

Let two variables s=0 and e=n-1.
While s<=e
Loop
    If Way[s][e]==0 Then X[s] should be included in the result and we store it in our result array.
    Else if Way[s][e]==1 Then X[s] should not be include in the result and update e=e-1 (because our result comes from case 4).
    Else if Way[s][e]==2 Then X[s] should not be include in the result and update s=s+1 (because our result comes from case 5).

The loop should be terminated when s>e. In that way we can get half part of the result and we can easily extend it to get the whole result.