5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组l

s.charAt(i) 每次都会检查数组下标越界，因此先转换成字符数组

回文天然具有「状态转移」性质：一个长度严格大于 2 的回文去掉头尾字符以后，剩下的部分依然是回文。反之，如果一个字符串头尾两个字符都不相等，那么这个字符串一定不是回文。「动态规划」的方法根据这样的性质得到。

动态规划

dp[i][j] 表示子串 s[i...j] 是否是回文串，不是 s[i...j] 中最长回文子串的长度！

遍历左右边界，右边界一定大于等于左边界，所以只需要遍历对角线上面的元素， 注意到dp[i][j]依赖于dp[i+1][j-1]，所以我们需要倒序遍历 i，然后正序遍历 j。

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length(); // 获取输入字符串的长度
        int left = 0, right = 0; // 初始化最长回文子串的左右边界
        int res = 0; // 记录最长回文子串的长度
        // 重点。dp[i][j] 表示子串 s[i...j] 是否是回文串，不是 s[i...j] 中最长回文子串的长度！
        // 同回文子串题目中的dp数组
        boolean[][] dp = new boolean[len][len]; 

        // 从字符串末尾开始遍历到开头
        for (int i = len - 1; i >= 0; i--) {
            // 从 i 开始向右遍历到字符串的末尾
            for (int j = i; j < len; j++) {
                // 如果字符 s[i] 和 s[j] 相同，并且子串 s[i+1...j-1] 也是回文串，
                // 或者 j - i <= 1（即子串长度为 1 或 2），则 s[i...j] 是回文串。重点！
                if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])) {
                    dp[i][j] = true; // 标记当前子串为回文串
                    // 如果当前回文子串长度大于已记录的最长回文子串长度
                    if (j - i + 1 > res) {
                        res = j - i + 1; // 更新最长回文子串的长度
                        left = i; // 更新最长回文子串的左边界
                        right = j; // 更新最长回文子串的右边界
                    }
                }
            }
        }
        
        // 根据记录的左右边界返回最长回文子串
        // substring 方法的第二个参数是子串结束的下一个位置，因此需要加 1。即左闭右开。
        return s.substring(left, right + 1);
    }
}

• 时间复杂度：O(n^2)，其中 n 是字符串的长度。动态规划的状态总数为 O(n^2)，对于每个状态，我们需要转移的时间为 O(1)。
• 空间复杂度：O(n^2)，即存储动态规划状态需要的空间。

中心扩展，贪心

从头开始顺序遍历，对每个字符，从当前字符往外扩展，得到奇数长度的字符串，从当前字符和它的后面一个字符往外扩展，得到偶数长度的字符串，取最长的字符串。

class Solution {
    // 寻找最长回文子串
    public String longestPalindrome(String s) {
        // 如果输入字符串为空或长度小于1，则返回空字符串
        if (s == null || s.length() < 1) {
            return "";
        }
        
        // 初始化起始和结束索引
        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 + 1) {
                // 更新起始和结束索引
                // 以aabaa和aabbaa为例，第一个字符串的i=2，len=5，
                // (len-1)/2计算的是aa的长度，其中减去的1代表b。
                // 第二个字符串的i=2，指向第一个b，(len-1)/2计算的也是aa的长度，它减去1是在减去第一个b。
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        // 返回最长回文子串
        return s.substring(start, end + 1);
    }

    // 从指定位置向两边扩展，寻找原字符串中以该字符为中心的最长回文子串的长度
    public int expandAroundCenter(String s, int left, int right) {
        // 当左指针不越界且右指针不越界且左右指向的字符相等时，继续向外扩展
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left; // 左指针左移
            ++right; // 右指针右移
        }
        // 返回回文串的长度（右指针位置减左指针位置再减1）
        return right - left - 1; // (right-1)-(left+1)+1
    }
}

• 时间复杂度：$O(n^2)$，其中 n 是字符串的长度。长度为 1 和 2 的回文中心分别有 n 和 n-1 个，每个回文中心最多会向外扩展 O(n) 次。
• 空间复杂度：O(1)。