generate longest possible palindrome for a given string

Question

I've been trying to generate the longest possible palindrome included in a given string, in java. But, it always ended up in errors.

Let me provide the sample input and output so that it may help .

Input: This is a sample string for testing

Output: ttissaepeassitt

It would be great if anyone could solve me this!!

Thank You!!

Answer 1

You could use a recursive algorithm:

public String findPalindrom(String input){
   String palindrom = "";
   for(int i=0; i<input.length(); i++){
      char c = input.charAt(i); // Explore the string from the beginning, char by char
      for(int j=input.length()-1; j>i; j--){ // Explore the string from the end, char by char
         if(input.charAt(j)==c){ // We found a letter for the palindrom
            String newPalindrom = c + findPalindrom(input.substring(i+1, j)) + c;
            if(newPalindrom.length() > palindrom.length())
               palindrom = newPalindrom;
         }
      }
   }
   if(palindrom.length()==0 && input.length()>0)
      palindrom += input.charAt(0); // manage the case where the only palindrom possible is a single char.
   return palindrom;
}