I take @kingwolfofsky 's solution as as a reference, and give my java version solution.

reference: https://discuss.leetcode.com/topic/3338/share-an-o-n-solution/8

the key point of this solution is Manacher's algorithm. we can google it if we don't know it.

```
public class Solution {
// Manacher's ALGORITHM
public String longestPalindrome(String s) {
if (s==null || s.length() == 0) return "";
int strLen = s.length();
int externLen = (strLen << 1) + 1;
char[] charArr = new char[externLen];
int idx = 0;
for (char ch : s.toCharArray()) {
charArr[idx++] = '#';
charArr[idx++] = ch;
}
charArr[idx] = '#';
int[] dp = new int[externLen];
int center=0, maxLen = 0;
int pivot=0, maxPos=0;
dp[0] = 1;
for (int i=1; i < externLen; i++) {
// this is key point to reach real O(n) time complex
dp[i] = (maxPos > i)? Math.min(dp[(pivot << 1) - i], maxPos-i):1 ;
while (i + dp[i] < externLen && i-dp[i] >= 0 && charArr[i+dp[i]] == charArr[i-dp[i]]) {
dp[i]++;
}
if (i+dp[i] > maxPos) {
maxPos = i+dp[i];
pivot = i;
}
if (dp[i] > maxLen) {
maxLen = dp[i];
center = i;
}
}
return s.substring( (center - maxLen + 1)>>>1 , (center + maxLen - 1)>>>1);
}
}
```