2

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?

Improve this question
14
  • I am not sure if I understand your question. For string 'abcde' would you be generating the palindrome 'c' or 'abcdedcba' ? Commented Apr 25, 2015 at 17:58
  • @RavindraHV see the last part of the question. I edited it. Commented Apr 25, 2015 at 18:12
  • I assume you want the longest possible palindrome? Commented Apr 25, 2015 at 18:15
  • 1
    @maraca the correct term is subsequence: en.wikipedia.org/wiki/Subsequence Commented Apr 25, 2015 at 18:36
  • 1
    I think this can be solved by applying a Longest Common Subsequence algorithm on the string and its reverse. Commented Apr 25, 2015 at 18:38

1 Answer 1

Reset to default
3

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).

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.