# Java based O(N) solution using Manacher's algorithm

• The description about manacher's algorithm which is the best solution for Longest Palindromic Substring can be found here https://discuss.leetcode.com/topic/80861/java-o-n-solution-based-on-manacher-s-algorithm-faster-than-97-16

For this solution I am trying to find the longest palindrome starting with the first postion which is done in O(n) time then I take the rest of the string except this palindrome in the original string and append the string to the beginning of the original string.

``````public class Solution {
public String shortestPalindrome(String s) {
if(s==null||s.length()<=1)
return s;
String fromBeingingLongest = longestPalindrome(s);
}
public String longestPalindrome(String s) {
if(s==null||s.length()<=1)
return s;
char[] sArray= s.toCharArray();
char[] s2Array = new char[2*sArray.length+1];
for(int i=0;i<s2Array.length-1;i+=2){
s2Array[i]='|';
s2Array[i+1]=sArray[i/2];
}
s2Array[s2Array.length-1]='|';
int[] dp = new int[s2Array.length];
int c=0,r=0;
int m=0,n=0;
int len = 0, pos = 0;
for(int i=1;i<s2Array.length;i++){
if(i>r-1){
dp[i]=0;
m=i-1;
n=i+1;
}else{
int i2=c*2-i;//c-dp[c]+r-i = c-dp[c]+dp[c]+c-i
if(dp[i2]+i<r){
dp[i]=dp[i2];
m=-1;
}else {
dp[i]=r-i;
n = r+1;
m = i*2-n;
}
}
while(m>=0&&n<s2Array.length&&s2Array[m]==s2Array[n]){
dp[i]++;
m--;
n++;
}
if(r<i+dp[i]){
c=i;
r=i+dp[i];
}
if(i>s2Array.length-1 && dp[i]>(s2Array.length-i)/2){
break;
}
}
for(int i=0;i<dp.length;i++){
if(i-dp[i]==0 && len<dp[i]){
len=dp[i];
pos=i;
}
}
char[] resultTemp = Arrays.copyOfRange(s2Array, pos-len, pos+len+1);
char[] result = new char[(resultTemp.length-1)/2];
for (int i = 0; i<result.length; i++) {
result[i] = resultTemp[i*2+1];
}
return String.valueOf(result);
}
}
``````

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