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


  • 1

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

Log in to reply
 

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