# Java Solution(99.03%)- O(N) easy to understand

• This solution is based on Manacher's algo.

// Solution
public class Solution {
/*
Solving the code using Manacher's Algo.
/
public String longestPalindrome(String s)
{
// Declare Variables
int index = 0; // index for the outer loop
int max_length = 0, center = 0; // store the max values
int length = s.length();
int i = 0; // for inner loops
if(s.length() == 0) return s; // null string
char[] a = new char[2
length + 1]; // Convert string From abccba to \$a\$b\$c\$c\$b\$a\$// this makes all palindromes of odd length
int temp_length = 2*length+1;
int[] palLength = new int[temp_length]; // Store the length of palindrome at the index equal to the center of the pallindrome
//~Declare Variables

``````     // fill the temp array -- abccba to \$a\$b\$c\$c\$b\$a\$
for(i = 0; i < length; i++)
{
a[2*i+1] = s.charAt(i);
}
palLength[0] = 1;
// outer Loop
while(index < temp_length)
{
int currentlength = longestPalindrome_withcentre(a,index,palLength[index]);
palLength[index] = currentlength;
if(currentlength > max_length)
{
center = index;
max_length = currentlength;
}
// We can skip a few indexs -- Manacher's Algo...
if(index + currentlength/2 == temp_length) break;
// find the next centre
for(i = 1; i <= currentlength/2 - 1; i++)
{
palLength[index + i] = palLength[index - i];
if(palLength[index - i]/2 + i == currentlength/2)
{
// Only this case is not to be skipped.
break;
}
if(palLength[index - 1]/ 2 + i > currentlength/2)
{
palLength[index+i] = (currentlength/2 - i)*2 + 1;
}
}
// skip indexes.
index += i;
}
int startpoint = center - max_length/2;
return s.substring(startpoint/2,startpoint/2 + max_length/2);
}
public int longestPalindrome_withcentre(char[] s, int index, int minLength)
{
int length_even = minLength;
int left_ptr = index - 1 - minLength/2;
int right_ptr = index + 1 + minLength/2;
while(left_ptr >= 0 && right_ptr < s.length)
{
if(s[left_ptr] != s[right_ptr])
break;
length_even += 2;
left_ptr--;
right_ptr++;
}
return length_even;
}
``````

}

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