java - Forming Palindrome from a String -

i solving longest palindrome in string problem, searching longest substring forming palindrome. code above :

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 2 characters , both same     if (ch[i] == ch[j] && + 1 == j)         return 2;      // if first , last characters match     if (ch[i] == ch[j])         return palindrome(ch, + 1, j - 1) + 2;      // if first , last characters not match     return max(palindrome(ch, i, j - 1), palindrome(ch, + 1, j));  } 

now, curious know if instead of finding longest substring, make palindrome choosing random characters (just 1 instance of each) string in same sequence in string. possible in polynomial time?

this problem can solved applying longest common subsequence algorithm (lcs). lcs solves following problem:

given 2 strings a , b, longest string c subsequence of both a , b?

a subsequence of string sequence of characters string, in order, skipping allowed.

now let @ problem. want find longest subsequence of string x palindrome. but, definition, palindrome string read same forward , backward. thus, same palindrome subsequence of mirror image of x.

let illustrate string abca. clearly, 2 longest palindromic subsequences aba , aca. mirror image of abca acba. longest palindromic subsequences? aba , aca!

so can use lcs solve problem follows:

string longestpalindromicsubsequence(string x) {     // mirror image of x     string y = mirror(x);     return lcs(x,y); } 

lcs can done in o(n^2) time, n length of string. reversing string takes linear time, final running time o(n^2).