# a java O(n) solution with Manacher's algorithm that beats 99.8%

• 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);
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.