Longest Palindrome In The String

INPUT :
A string of length n.

OUTPUT :
A palindromic string which is the longest sub-string of the inputted string. Thus the output string can have a maximum length of 'n'

THE BRUTE FORCE METHOD :
Since we are looking for a sub-string, the brute force method would suggest finding every possible sub-string in the string and checking if its a palindrome. The algorithm to find every sub-string accepts the inputted string 's' and its length 'n' as parameters. We assume the existence of a pseudo function isPalindrome which accepts a string as parameter and returns true if the string is a palindrome and false otherwise. We also assume subString(String, startIndex, endIndex) to be a function that returns the substring of s beginning from startIndex (including) and ending at endIndex (excluding). This is quite similar to the Java.lang.String.substring(int beginIndex, int endIndex). The algorithm uses 3 variables : maxlen to find out the maximum length of the palindrome, templen to compare with maxlen, start and end as the begin and end indices of the palindrome respectively.

Algorithm findSubString (String s)

1. maxlen = 0 ,  templen = 0, start = 0, end = 0
2. for (int i = 0 up to n-1) 
3.      for (int j = i down to 0)
4.            for (int k = i+1 up to n)
5.                          templen = k-j+1
6.                          if ( isPalindrome(subString(s, j, k+1)) && templen > maxlen) 
7.                               maxlen = templen
8.                               start = j
9.                               end = k+1 // k+1 is because subString excludes the endIndex
10.                          end if
11.               end for
12.         end for
13. end for
14. return subString(s, start, end)

However, as we see, this approach uses 3 traversals in 3 nested for loops, taking O(n³) time. It should be noted that the time-efficiency of the function isPalindrome() is not taken into consideration as it is, anyways, less than O(n³) (shall be proved in a few moments).

THE isPalindrome() FUNCTION :
The most efficient method of determining whether a string is palindrome or no is to start with its central character and to go one character each to the left and right simultaneously checking whether the string is a palindrome. For example, for "abcba", we start at "c", which is the central character and then go one character to the left getting "b" and one character to the right getting "b" again. Thus "bcb" is a palindrome. We go on doing this till the string stops being a palindrome. This is essentially the algorithm behind isPalindrome(). Let us say that we divide every palindromic string of length, say p, into 2 kinds : when p is even and when p is odd. 

1.  when p is odd, as in "abcba", we fix 1 mid-point (here "c"), then compare every character at an "x" distance from it to the left to every character at the same distance from it to the right.
2. when p is even, like "abccba", we fix no mid-point, and begin comparing from "c" and "c" (they occupy the center positions in the string; 6/2 = 3 therefore 3rd and 4th positions are central) and then continue as above.

Thus we see, that any string can be checked for palindrome in O(n) times (1 traversal).

A BETTER APPROACH :
Note that we need to find a palindromic sub-string. Such a sub-string may begin or end at any index in the string, and not necessarily at the beginning and the end of the string. For example, for "banana", the longest palindromic sub-string is "anana" which doesn't start at the beginning of the string. So to speak, we do not know the start or the end of the sub-string and thus we cannot find the mid-point. Hence, we need to consider every character as the mid-point and begin checking for the palindromes. This will take 1 traversal of the string. A java code implementing this approach is as follows :

Do leave any comments if you find a better approach or if you have any doubts regarding the given approach. 

Courtesy : http://www.geeksforgeeks.org/longest-palindrome-substring-set-1/