最长回文子串

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

回文串指的是正着读和反着读都相同的字符串。

子串必须是原字符串中连续的一段。

示例 1：

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

示例 2：

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

提示：

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

解法一（中心扩展）：

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        int start = 0;
        int end = 0;

        for (int i = 0; i < n; i++)
        {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = max(len1, len2);

            if (len > end - start + 1)
            {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

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

private:
    int expandAroundCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right])
        {
            left--;
            right++;
        }

        return right - left - 1;
    }
};

解法二（动态规划）：

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));

        int start = 0;
        int maxLen = 1;

        for (int len = 1; len <= n; len++)
        {
            for (int left = 0; left + len - 1 < n; left++)
            {
                int right = left + len - 1;

                if (s[left] != s[right])
                {
                    dp[left][right] = false;
                }
                else if (len <= 3)
                {
                    dp[left][right] = true;
                }
                else
                {
                    dp[left][right] = dp[left + 1][right - 1];
                }

                if (dp[left][right] && len > maxLen)
                {
                    start = left;
                    maxLen = len;
                }
            }
        }

        return s.substr(start, maxLen);
    }
};

核心思想

这题要求的是最长回文子串，而且子串必须连续。

直接想法是枚举所有子串，再判断每个子串是不是回文。

但是长度最多为 1000，枚举子串再逐个判断会达到 O(n^3)，没有必要。

回文串有一个很重要的特点：

一个回文串一定有中心，并且从中心向左右两边扩展时，左右字符始终相等。

所以可以枚举每一个可能的中心，然后向左右两边扩展，找到以这个中心为核心的最长回文串。

由于回文串长度可能是奇数，也可能是偶数，所以每个位置要考虑两种中心：

• 奇数长度：中心是一个字符，例如 "aba"
• 偶数长度：中心是两个字符之间，例如 "bb"

解法一：中心扩展

中心扩展的核心函数是：

int expandAroundCenter(const string& s, int left, int right)

其中：

• left 表示当前扩展的左边界
• right 表示当前扩展的右边界

只要满足：

left >= 0 && right < s.size() && s[left] == s[right]

说明当前 [left, right] 仍然是回文串，可以继续向外扩展：

left--;
right++;

当循环结束时，说明已经扩展到了不合法的位置。

此时真正的回文串范围是：

[left + 1, right - 1]

长度是：

right - left - 1

为什么要扩展两次

回文串的中心有两种。

1. 奇数长度回文

例如：

"bab"

中心是中间的 'a'。

所以从同一个位置开始扩展：

expandAroundCenter(s, i, i)

2. 偶数长度回文

例如：

"bb"

中心在两个 'b' 中间。

所以从相邻两个位置开始扩展：

expandAroundCenter(s, i, i + 1)

对每个下标 i 都尝试这两种扩展，就能覆盖所有可能的回文子串。

如何更新答案边界

中心扩展得到当前最长长度 len 后，如果它比当前答案更长，就更新答案的左右边界。

代码中使用：

start = i - (len - 1) / 2;
end = i + len / 2;

这个公式可以同时处理奇数长度和偶数长度。

例如：

• 如果 len = 3，中心是 i，范围是 [i - 1, i + 1]
• 如果 len = 2，中心在 i 和 i + 1 之间，范围是 [i, i + 1]

最终返回：

s.substr(start, end - start + 1)

解法二：动态规划

动态规划的思路是判断每个子串 s[left...right] 是否为回文串。

如果知道中间部分：

s[left + 1 ... right - 1]

是不是回文串，那么只要再比较两端字符 s[left] 和 s[right]，就能判断整个子串是不是回文。

状态定义

定义：

dp[left][right] 表示子串 s[left...right] 是否为回文串。

如果 dp[left][right] == true，说明从 left 到 right 的连续子串是回文串。

答案就是所有 dp[left][right] == true 的子串中长度最大的那个。

递推公式推导

对于子串 s[left...right]：

如果两端字符不同：

s[left] != s[right]

那么它一定不是回文串：

dp[left][right] = false

如果两端字符相同，还要看子串长度。

当长度小于等于 3 时，只要两端相同，中间最多只有一个字符，一定是回文：

"a"
"aa"
"aba"

所以：

dp[left][right] = true

当长度大于 3 时，必须要求中间部分也是回文：

dp[left][right] = dp[left + 1][right - 1]

综合起来：

if (s[left] != s[right])
{
    dp[left][right] = false;
}
else if (len <= 3)
{
    dp[left][right] = true;
}
else
{
    dp[left][right] = dp[left + 1][right - 1];
}

为什么按长度递推

dp[left][right] 依赖的是：

dp[left + 1][right - 1]

这个子串比当前子串短 2。

所以必须先计算短子串，再计算长子串。

代码中按长度 len 从 1 到 n 枚举：

for (int len = 1; len <= n; len++)

这样在计算长度为 len 的子串时，它依赖的长度为 len - 2 的子串已经计算完成。

边界情况

如果字符串长度为 1，单个字符本身就是回文串，答案就是它自己。

中心扩展中，初始答案范围是 [0, 0]，可以直接返回第一个字符。

动态规划中，长度为 1 的子串会被标记为回文。

如果字符串中所有字符都不相同，最长回文子串长度就是 1。

如果存在多个长度相同的最长回文子串，返回其中任意一个都符合题意。

正确性证明

我们证明：中心扩展和动态规划都能返回一个最长回文子串。

结论 1：任意回文子串都会被中心扩展枚举到

任意一个回文子串都有中心。

如果它的长度是奇数，那么中心是某一个字符。

算法会在遍历到这个字符时调用：

expandAroundCenter(s, i, i)

如果它的长度是偶数，那么中心在两个相邻字符之间。

算法会在遍历到左侧字符时调用：

expandAroundCenter(s, i, i + 1)

因此任意回文子串的中心都会被算法枚举到。

结论 2：中心扩展能找到固定中心下的最长回文子串

对于固定中心，算法不断比较左右两侧字符。

只要字符相等，就继续向外扩展。

一旦越界或两侧字符不相等，就停止。

停止时，再向外扩展已经不可能保持回文性质。

因此算法得到的就是这个中心下能形成的最长回文子串。

结论 3：中心扩展取最大值后得到全局最长回文子串

由结论 1 可知，任意回文子串都会在某个中心被枚举到。

由结论 2 可知，每个中心都会得到该中心下的最长回文子串。

算法在所有中心的结果中取最长者。

因此返回的子串一定是全局最长回文子串之一。

结论 4：动态规划状态转移正确

对于任意子串 s[left...right]：

如果 s[left] != s[right]，两端不同，不可能是回文串。

如果 s[left] == s[right] 且长度不超过 3，中间没有字符或只有一个字符，所以一定是回文串。

如果 s[left] == s[right] 且长度大于 3，整个子串是否回文只取决于中间子串 s[left + 1...right - 1] 是否回文。

这正是动态规划的转移规则。

结论 5：动态规划会记录所有回文子串中的最长者

动态规划按长度从短到长枚举所有子串。

每个子串是否为回文都由结论 4 正确判断。

一旦发现回文子串，并且长度超过当前答案，就更新答案。

因此最终记录的一定是最长回文子串。

得出结论

由结论 1、结论 2 和结论 3 可知，中心扩展解法正确。

由结论 4 和结论 5 可知，动态规划解法正确。

因此两个解法都能返回一个符合题意的最长回文子串。

举例理解

以：

s = "babad"

为例。

枚举中心并扩展：

最终返回 "bab" 或 "aba" 都可以。

再看：

s = "cbbd"

当中心在两个 'b' 中间时：

c [b b] d

可以扩展出 "bb"。

继续向外比较 'c' 和 'd'，不相等，扩展停止。

所以最长回文子串是：

"bb"

复杂度分析

设字符串长度为 n。

解法一

一共有 2n - 1 个可能的回文中心。

每次中心扩展最坏需要 O(n)。

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

解法二

需要枚举所有子串状态，一共有 O(n^2) 个。

动态规划表大小也是 O(n^2)。

• 时间复杂度：O(n^2)
• 空间复杂度：O(n^2)

本题 n <= 1000，中心扩展已经可以通过，并且空间复杂度更优，是更推荐的写法。