本文共 1892 字，大约阅读时间需要 6 分钟。

????????

??????? s??? s ???????????????????? O(n^3)?????????????????????????????????????????

1. ???????

?????????????????????????????"aba" ? "bb" ???????

2. ????????

??????????????????????????????? O(n^3)?????? 1000 ??????????????????

3. ???????

????????????????Manacher's Algorithm????????? O(n^2)????????????

4. ????????

??????????????????????????????????????????????????????????????????

5. ????

????????????

public class Solution5 {
    public static String longestPalindrome(String s) {
        int n = s.length();
        if (n == 0) {
            return "";
        }
        int max = 0;
        int start = 0;
        int end = 0;
        // ??????????
        for (int i = 0; i < n; i++) {
            // ????????? s[i]
            int left = i;
            int right = i;
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            // ????????
            if (right - left - 1 > max) {
                max = right - left - 1;
                start = left + 1;
                end = right - 1;
            }
            // ???????????
            if (i + 1 < n) {
                int left1 = i + 1;
                int right1 = i;
                while (left1 >= 0 && right1 < n && s.charAt(left1) == s.charAt(right1)) {
                    left1--;
                    right1++;
                }
                if (right1 - left1 - 1 > max) {
                    max = right1 - left1 - 1;
                    start = left1 + 1;
                    end = right1 - 1;
                }
            }
        }
        return s.substring(start, end + 1);
    }
}

6. ????

7. ????

??????????????????? O(n^2)??????????????????

8. ??

??????????????????????????????????????????????????