### [AMAZON]Longest palindrome substring

Given a string S, find the longest palindromic substring in S.

1. We can expand the string around its palindromic centre.There are a total of 2*n-1 palindromic centres in the string.This way all odd and even length palindromes are handled. Time complexity-O(n^2). Space complexity- O(1)

The best known algorithm is linear time Manacher's Algorithm.
Linear time with O(n) space complexity.

2. static String longestPalindrome(String string){
if(string == null) return string;
if(string.length() == 1) return string;

String str = "";
for (int i = 0; i < string.length(); i++) {
str += "#" + string.charAt(i);
}
str += "#";

int[] p = new int[str.length()];

int maxIndex = -1;
int maxValue = -1;
for (int i = 0; i < str.length(); i++) {
if(i == 0) p[i] = 1;
else if(maxIndex > -1 && p[maxIndex]/2 + i > str.length()) continue;
else{
int c = 1;
for (int j = i-1, k = i+1; j >= 0 && k < str.length(); j--,k++) {
if(str.charAt(j) == str.charAt(k))
c += 2;
}
p[i] = c;
if(maxValue < c){
maxIndex = i;
maxValue = p[i];
}
}
}
str = str.substring(maxIndex-maxValue/2, maxIndex+maxValue/2+1).replaceAll("\\#", "");
return str;
}