CareerCup

String S1;
Reverse of String S2;
Find the longest common subsequence of S1 and S2.
The subsequence will be a longest palindrome.
The algorithm takes a complexity of n^2, n being the length of the string.

Using suffix tree, you can reduce the complexity to O(n).

no point of writing code as your reply .. just explain the algorithm , that would be of great help , its tough to interpret what you wrote in your program .. so its always preferrable to explain your algorithm .. so that others can easily code your algorithm if needed .

largestPalindrome = "";
for(int i =0;i<n;i++)
int left = i-1;
int right = i+1;
while(left>=0 && right < n && s.charAt(left) == s.charAt(right))
String palindrome = s.substring(left,right+1);
largestPalindrome = palindrome.length() > largestPalindrome.length() ? palindrome : largestPalindrome
left--;
right+;

return largestPalindrome

int getLenOfMaxPalindrom(char * str, int index){
  int startFlag=0;
  int evenFlag=0;
  int len=0;
  int evenMax,oddMax;
  while ( str[len++] != '\0' );
  len--;
  if (!index  || index==len-1)
    return 1;
  // check for odd palindrom
  oddMax=0;
  while ( index+oddMax<len && index-oddMax>=0 && ( str[index-oddMax-1] == str[index+oddMax+1] ))
    oddMax++;
  // check for even palindrom
  evenMax=0;
  while ( index+evenMax-1<len && index-evenMax>=0 && ( str[index-evenMax-1] == str[index+evenMax] ))
    evenMax++;
  //return count*startFlag*2+(!evenFlag);
  if ( evenMax == 0 && oddMax == 0 )
    return 1;
  return evenMax>oddMax?evenMax*2:oddMax*2+1;
}
void printLongestPalindrom(char * str){
  int longestIndex=0;
  int longestLen=1;
  int i,tempLen,len=0;
  while ( str[len] != '\0' ){
    tempLen=getLenOfMaxPalindrom(str,len);
//    printf("for index %d, longest palindrom = %d\n",len,tempLen);
    if ( tempLen>longestLen ){
      longestLen=tempLen;
      longestIndex=len-tempLen/2;
    }
    len++;
  }
  for ( i=0 ; i<longestLen ; i++ )
    printf("%c",str[i+longestIndex]);
  printf("\n");
}

Hint : s1 given string,Take reverse string as s2...compare each char of s1 with s2...if matches check for palindrome...O(n2)

do we need to handle this?

s1: deabcba
s2 (reverse of s1): abcbaed

I expected to return the answer, abcba. Do i understand correctly?

Use recursion and mid value of the string and note the start and end index positions of all possible palindromes. max(end index-start index position) value gives the length of the longest palindrome and moreover as we have start and end index we can extract the exact palindrome from the string ....

Read Manachar's Algorithm from wiki

or google for longest palindrome in a string , good explaination is given at leetcode.com

Not my code. But i made little bit correction. from stackoverflow:

/**
 * Created by IntelliJ IDEA.
 * User: elbek
 * Date: 6/3/12
 * Time: 7:02 PM
 * To change this template use File | Settings | File Templates.
 */
public class Test {
    /**
     * @param input is a String input
     * @return The longest palindrome found in the given input.
     */
    public static String getLongestPalindrome(final String input) {
        int rightIndex = 0, leftIndex = 0;
        String currentPalindrome = "", longestPalindrome = "";
        for (int centerIndex = 1; centerIndex < input.length() - 1; centerIndex++) {

            if (centerIndex >= 0 && centerIndex < input.length() - 2) {
                if (input.charAt(centerIndex) == input.charAt(centerIndex + 1)) {

                    leftIndex = centerIndex;
                    rightIndex = centerIndex + 1;

                } else {
                    leftIndex = centerIndex - 1;
                    rightIndex = centerIndex + 1;
                }
            }

            while (leftIndex >= 0 && rightIndex < input.length()) {
                if (input.charAt(leftIndex) != input.charAt(rightIndex)) {
                    break;
                }
                currentPalindrome = input.substring(leftIndex, rightIndex + 1);
                longestPalindrome = currentPalindrome.length() > longestPalindrome.length() ? currentPalindrome : longestPalindrome;
                leftIndex--;
                rightIndex++;
            }
        }
        return longestPalindrome;
    }

    public static void main(String... args) {
        String str = "12345678987654321ZWETYGDE";
        String longestPali = getLongestPalindrome(str);
        System.out.println("String: " + str);
        System.out.println("Longest Palindrome: " + longestPali);
    }
}