# Java easy-understanding solution. Beats 97%

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

• 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 length `len >= 2` ending at `i` implies three things:

1. `i - len + 1 >= 0` (obviously).
2. `s[i - len + 1] == s[i]`.
3. `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 length `len - 2` ending at `i - 1`, then we may find another one of length `len` ending at `i`. So incrementing `i` by 1 can lead to increase of the palindrome length by 2. One more important corollary: if we find a palindrome of length `len - 2` at `i - 1`, then we only need to check the conditions (1) and (2) above on the next iteration—we may skip the `isPalindrome()` 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 substring `s[0..i)` (exclusive). Let's deal with it rigorously, CLR-style:

1. Initialization. This is obviously true for `i = 0` if we initialize `max = 0`. The longest palindrome substring of an empty string `s[0..0)` is an empty string.
2. Maintenance. Suppose `max` is the longest palindrome substring of `s[0..i)`. Then for `s[0..i+1)` we only need to consider palindromes ending at `s[i]` (inclusive), because we've checked all others already. From the fact (3) above it follows that we can only find palindromes of length `max + 1` or `max + 2` ending there. Indeed, if we were able to find a palindrome of length `max + l` (l > 2) ending at `i`, then it would mean that there is a palindrome of length `max + l - 2 > max` ending at `i - 1`, which contradicts the assumption that `max` is the maximum length of a palindrome found so far.
3. Termination. Since the substring `s[0..N)` (N = length of `s`) is the string `s` itself, then `max` 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;
}
``````

• @leetin16, see my answer below.

• clever!!!!!!!!!!!!!!!

• @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

• Awesome code!