Forming Palindrome from a String

Question

I was solving Longest Palindrome in a String problem, where we are searching for the longest substring forming a palindrome. My code for the above is :

private static int palindrome(char[] ch, int i, int j) {
    // TODO Auto-generated method stub
    if (i == j)
        return 1;

    // Base Case 2: If there are only 2 characters and both are same
    if (ch[i] == ch[j] && i + 1 == j)
        return 2;

    // If the first and last characters match
    if (ch[i] == ch[j])
        return palindrome(ch, i + 1, j - 1) + 2;

    // If the first and last characters do not match
    return max(palindrome(ch, i, j - 1), palindrome(ch, i + 1, j));

}

Now, I am curious to know that if instead of finding the longest substring, we make a palindrome choosing random characters (just one instance of each) from the string but in the same sequence as in String. Is it possible to do this in polynomial time?

Answer 1

This problem can be solved by applying the Longest Common Subsequence algorithm (LCS). LCS basically solves the following problem:

Given two strings a and b, what is the longest string c that is a subsequence of both a and b?

A subsequence of a string is a sequence of characters from that string, in order, where skipping is allowed.

Now let us look at your problem. We want to find the longest subsequence of a string x that is a palindrome. But, by definition, a palindrome is a string that is read the same forward and backward. Thus, the same palindrome will also be a subsequence of the mirror image of x.

Let us illustrate with the string abca. Clearly, its two longest palindromic subsequences are aba and aca. The mirror image of abca is acba. What are its longest palindromic subsequences? Also aba and aca!

So we can now use LCS to solve your problem as follows:

String longestPalindromicSubsequence(String x) {
    // Get the mirror image of x
    String y = mirror(x);
    return LCS(x,y);
}

LCS can be done in O(n^2) time, where n is the length of the string. Reversing a string takes linear time, so the final running time is O(n^2).