public String longestPalindrome(String s) {
char[] ca = s.toCharArray();
int rs = 0, re = 0;
int max = 0;
for(int i = 0; i < ca.length; i++) {
if(isPalindrome(ca, i  max  1, i)) {
rs = i  max  1; re = i;
max += 2;
} else if(isPalindrome(ca, i  max, i)) {
rs = i  max; re = i;
max += 1;
}
}
return s.substring(rs, re + 1);
}
private boolean isPalindrome(char[] ca, int s, int e) {
if(s < 0) return false;
while(s < e) {
if(ca[s++] != ca[e]) return false;
}
return true;
}
Java easyunderstanding solution. Beats 97%


Explanation for those interested. For every position
i
we're interested if there's a palindrome ending at this position (inclusive) longer than the longest palindrome found so far.For
i = 0
the only palindrome ending there is the palindrome of length 1. So the new palindrome has length 1 and therefore the maximum increases by 1.For every
i > 0
we can have many palindromes ending there. We're only interested in those with length >= 2 because we've already found one of length 1. Some of palindromes may have even lengths, some odd. The presence of a palindrome of lengthlen >= 2
ending ati
implies three things:i  len + 1 >= 0
(obviously).s[i  len + 1] == s[i]
.s[i  len + 2 .. i  1]
is a palindrome. This is the most interesting fact because it means that if we have found a palindrome of lengthlen  2
ending ati  1
, then we may find another one of lengthlen
ending ati
. So incrementingi
by 1 can lead to increase of the palindrome length by 2. One more important corollary: if we find a palindrome of lengthlen  2
ati  1
, then we only need to check the conditions (1) and (2) above on the next iteration—we may skip theisPalindrome()
call.
Now consider the following loop invariant: just prior to the first iteration, and right after each iteration (after incrementing
i
)max
is the length of the longest palindrome substring within the substrings[0..i)
(exclusive). Let's deal with it rigorously, CLRstyle: Initialization. This is obviously true for
i = 0
if we initializemax = 0
. The longest palindrome substring of an empty strings[0..0)
is an empty string.  Maintenance. Suppose
max
is the longest palindrome substring ofs[0..i)
. Then fors[0..i+1)
we only need to consider palindromes ending ats[i]
(inclusive), because we've checked all others already. From the fact (3) above it follows that we can only find palindromes of lengthmax + 1
ormax + 2
ending there. Indeed, if we were able to find a palindrome of lengthmax + l
(l > 2) ending ati
, then it would mean that there is a palindrome of lengthmax + l  2 > max
ending ati  1
, which contradicts the assumption thatmax
is the maximum length of a palindrome found so far.  Termination. Since the substring
s[0..N)
(N = length ofs
) is the strings
itself, thenmax
is the length of the longest palindrome substring. If we keep track of starts/ends, we can easily get the substring itself.
My code based on the above is given below. It differs from the solution presented in the question only in that it tries to optimize palindrome checks by using the fact (3) for the case when the previous palindrome is at
i  1
. This improves performance by 2 ms (total 7 ms, beating 99%).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; }


@SergeyTachenov Hi, your explanation is awesome! Can I ask what is the complexity of this solution?

@kevinscake I think its O(n^2)，because we must judge whether a substring is palindrome in each loop