Given a string X and the reverse of that string,Y. Is the longest common sequence of X and Y always a palindrome?

Question

Our professor gave us the following problem:

Input
   A sequence of characters X = x1, x2, ... ,xn
Output
   The length of the longest sub-sequence of X that is a palindrome

My solution was:

 Take X and reverse it into the sequence Y = y1, y2, ... , yn
 Then perform LongestCommonSubsequence(X,Y)  

He gave me partial credit and wrote,

"The LCS of X and reverse X is not necessarily a palindrome."

But I keep running the this algorithim (not mine by the way), with X and reverse X and all I get is palindromes.

/**
 ** Java Program to implement Longest Common Subsequence Algorithm
 **/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

/** Class  LongestCommonSubsequence **/
public class  LongestCommonSubsequence
{    
/** function lcs **/
public String lcs(String str1, String str2)
{
    int l1 = str1.length();
    int l2 = str2.length();

    int[][] arr = new int[l1 + 1][l2 + 1];

    for (int i = l1 - 1; i >= 0; i--)
    {
        for (int j = l2 - 1; j >= 0; j--)
        {
            if (str1.charAt(i) == str2.charAt(j))
                arr[i][j] = arr[i + 1][j + 1] + 1;
            else 
                arr[i][j] = Math.max(arr[i + 1][j], arr[i][j + 1]);
        }
    }

    int i = 0, j = 0;
    StringBuffer sb = new StringBuffer();
    while (i < l1 && j < l2) 
    {
        if (str1.charAt(i) == str2.charAt(j)) 
        {
            sb.append(str1.charAt(i));
            i++;
            j++;
        }
        else if (arr[i + 1][j] >= arr[i][j + 1]) 
            i++;
        else
            j++;
    }
    return sb.toString();
}
}

How can I prove or disprove that the longest common sub-sequence of X and reverse X is or isn't a palindrome?

Answer 1

For X = 0,1,2,0,1 we have Y = reverse(X) = 1,0,2,1,0 and one of the longest subsequences is 0,2,1. So your proposition does not hold in general. But it is still possible that the LCS returned by the algorithm given in the question is always a palindrome. In my example a systematic enumeration of all LCS-s looks like this: 0,1,0, 0,2,1, 0,2,0, 1,2,0, 1,2,1, 1,0,1 - and the first LCS is indeed a palindrome. But I was not able to proof in general yet. So I think that actually both (professor and you) are right: Although there can be a LCS of X and reverse(X) that is not a palindrome, most (actually: straight forward) implementations of an LCS-algorithm would always return a palindrome for X and reverse(X). (Full proof still missing)