Java easy-understanding solution. Beats 97%


  • 14
    Y
    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;
    }

  • 0
    L

    Explanation please!!


  • 15

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

  • 0

    @leetin16, see my answer below.


  • 0
    Z

    wonderful answer


  • 0

    clever!!!!!!!!!!!!!!!


  • 0
    K

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


  • 0
    L

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


  • 0
    Z

    Awesome code!


  • 0
    M

    Awesome answer!


Log in to reply
 

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