Tools Matter

suffix tree

public class Solution {
    public String longestPalindrome(String s) {
        if (s.length() <= 1) return s;
        String result = "";
        Node root = new Node();

        // original string
        for (int i = 0; i < s.length(); i++) {
            String subString = s.substring(i);
            Node node = root;
            for(int j = 0; j < subString.length(); j++) {
                if (node.nodeList.get(subString.charAt(j)) == null) {
                    Node leaf = new Node();
                    leaf.letter = subString.charAt(j);
                    leaf.isOriginal = 1;
                    node.nodeList.put(subString.charAt(j), leaf);
                }
                else {
                    node.nodeList.get(subString.charAt(j)).isOriginal = 1;
                }

                node = node.nodeList.get(subString.charAt(j));
            }
        }

        // reversed string
        String rs = new StringBuilder(s).reverse().toString();
        for (int i = 0; i < rs.length(); i++) {
            String subReversedString = rs.substring(i);

            Node node = root;
            String tmpString = "";

            for(int j = 0; j < subReversedString.length(); j++) {
                if (node.nodeList.get(subReversedString.charAt(j)) == null) {
                    Node leaf = new Node();
                    leaf.letter = subReversedString.charAt(j);
                    leaf.isOriginal = 0;
                    node.nodeList.put(subReversedString.charAt(j), leaf);
                }
                else {
                    // target node exists, and which is generated by the original string.
                    if (node.nodeList.get(subReversedString.charAt(j)).isOriginal == 1) {
                        tmpString += subReversedString.charAt(j);
                    }
                }
                node = node.nodeList.get(subReversedString.charAt(j));
            }
            
            if (tmpString.length() > result.length()) {
                result = tmpString;
            }
        }

        return result;
    }
}

class Node {
    char letter;
    int isOriginal;
    Map<Character, Node> nodeList = new HashMap<>();
}

normal

public class Solution {
    public String longestPalindrome(String s) {
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--; R++;
        }
        return R - L - 1;
    }
}

manacher’s algorithm

public class Solution {
    public String longestPalindrome(String s) {
        if (s.length() <= 2) return s;

        String separator = "@", starter = "^";
        StringBuilder stringBuilder = new StringBuilder(starter).append(separator);
        for (int i = 0; i < s.length(); i++) {
            stringBuilder.append(s.charAt(i)).append(separator);
        }

        String formattedString = stringBuilder.toString();
        int[] result = new int[formattedString.length()];
        // id stands for **the center of furthest palindrome string**
        // mx stands for **the right boundary of furthest palindrome string**
        int mx = 0, id = 0;

        for (int i = 1; i < formattedString.length(); i++) {
            if (mx > i) {
                result[i] = result[2*id - i] > mx - i ? mx - i : result[2*id - i];
            }
            else {
                result[i] = 1;
            }

            while ((i + result[i]) < formattedString.length() && (i - result[i]) >= 0
                    && formattedString.charAt(i + result[i]) == formattedString.charAt(i - result[i])) {
                result[i]++;
            }

            if (i + result[i] > mx) {
                mx = i + result[i];
                id = i;
            }
        }

        int maxIndex = 0, maxValue = 0;
        for (int k = 0; k < formattedString.length(); k++) {
            if (result[k] > maxValue) {
                maxIndex = k;
                maxValue = result[k];
            }
        }

        return formattedString
                .substring(maxIndex - result[maxIndex] + 1, maxIndex + result[maxIndex] - 1)
                .replace(separator, "");
    }
}

DP

public class Solution {
    public String longestPalindrome(String s) {
        if (s.length() <= 2) return s;

        int start = 0, end = 0;
        // matrix[x][y] stands for if s.substring(x, y + 1) is a palindrome string
        boolean matrix[][] = new boolean[s.length()][s.length()];

        for (int y = 1; y < s.length(); y++) {
            int x = 0;
            matrix[y][y] = true;
            while (x < y) {
                if (s.charAt(x) == s.charAt(y)) {
                    if ((y - x == 1) || matrix[x + 1][y - 1]) {
                        // is palindrome
                        matrix[x][y] = true;
                        // compare
                        if (y - x + 1 > end - start + 1) {
                            start = x;
                            end = y;
                        }
                    }
                }
                x++;
            }
        }

        return s.substring(start, end + 1);
    }
}

Reference:

leetcode articles

(Mandarin Chinese) Manacher’s ALGORITHM: O(n)时间求字符串的最长回文子串