# Three Java solutions—two O(n^2), one Manacher's

• My first solution was pretty naive, but still somewhat efficient (27 ms):

``````public String longestPalindrome(String s) {
int es = 0, ee = 0, os = 0, oe = 0; // even/odd starts/ends
char[] cs = s.toCharArray();
for (int i = 0; i < cs.length; ++i) {
if (ee - es >= Math.min(i + 1, cs.length - 1 - i) * 2
&& oe - os >= Math.min(i, cs.length - 1 - i) * 2 + 1) {
break;
}
int lenEven = 0;
for (int j = i, k = i + 1; j >= 0 && k < s.length() && cs[j] == cs[k]; --j, ++k) {
lenEven += 2;
}
if (lenEven > ee - es) {
es = i - lenEven / 2 + 1;
ee = i + lenEven / 2 + 1;
}
int lenOdd = -1;
for (int j = i, k = i; j >= 0 && k < s.length() && cs[j] == cs[k]; --j, ++k) {
lenOdd += 2;
}
if (lenOdd > oe - os) {
os = i - lenOdd / 2;
oe = i + lenOdd / 2 + 1;
}
}
return oe - os > ee - es ? s.substring(os, oe) : s.substring(es, ee);
}
``````

The next solution was based on this one, but slightly improved. 7 ms. For explanation, refer to my answer to that solution.

``````public String longestPalindrome(String s) {
int start = 0, end = 0;
char[] cs = s.toCharArray();
for (int i = 0, max = 0, prev = 0; i < cs.length; ++i) {
if (i - max - 1 >= 0 && cs[i - max - 1] == cs[i]
&& (prev == i - 1 || isPalindrome(cs, i - max, i))) {
start = i - max - 1;
end = i + 1;
max += 2;
prev = i;
} else if (isPalindrome(cs, i - max, i + 1)) {
start = i - max;
end = i + 1;
++max;
prev = i;
}
}
return s.substring(start, end);
}

private static boolean isPalindrome(char[] cs, int start, int end) {
for (int i = start, j = end - 1; i < j; ++i, --j) {
if (cs[i] != cs[j]) {
return false;
}
}
return true;
}
``````

And finally, Manacher's algorithm. Instead of creating a temporary string with boundary separators, I work with a virtual string here, where even indexes correspond to boundaries and odd indexes correspond to actual characters. But it's still pretty slow (13 ms), and I can't think of a way to make it faster.

``````public String longestPalindrome(String s) {
char[] cs = s.toCharArray();
int n = cs.length, m = cs.length * 2 + 1;
int[] p = new int[m]; // p[i] is the "radius" of the longest palindrome centered at i
int max = 0;
for (int i = 0, c = 0; i < m; ++i) { // c is the center of the rightmost palindrome
final int r = c + p[c]; // rightmost boundary found so far
int left, right;
if (i > r) { // outside of the known area
left = i - 1;
right = i + 1;
} else if (i + p[c - (i - c)] < r) { // palindrome doesn't go as far as r
p[i] = p[c - (i - c)];
left = right = -1; // skip the loop
} else { // palindrome goes to r, so it may extend beyond
p[i] = r - i;
left = i - p[i] - 1;
right = i + p[i] + 1;
}
while (left >= 0 && right < m && ((left & 1) == 0 || cs[left >> 1] == cs[right >> 1])) {
++p[i];
--left;
++right;
}
if (i + p[i] > r) {
c = i;
}
if (p[i] > p[max]) {
max = i;
}
}
return s.substring((max - p[max]) >> 1, (max + p[max] + 1) >> 1);
}
``````

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