好的，我们这次来详细学习 LeetCode 第 5 题「最长回文子串」。

1. 题目描述

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

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 也是一个有效答案。

示例 2：
输入：s = "cbbd"
输出："bb"

提示：

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

回文串：正着读和反着读都一样的字符串，比如 "aba"、"aa"、"a"。

2. 理解题意

我们要找的是原字符串的一个连续子串，并且这个子串是回文的，同时长度要最长。
可能有多个最长回文子串，返回任意一个即可。

3. 思路分析

3.1 暴力法（不可行但可理解）

最直接的想法是：

1. 枚举所有子串（起点 i，终点 j，且 j ≥ i），共有 O(n²) 个子串。
2. 对每个子串判断是否是回文，需要 O(n) 时间。
3. 总复杂度 O(n³)，在 n=1000 时显然会超时。

所以我们需要更高效的方法。

3.2 中心扩展法

核心观察：

• 回文串具有对称性，可以有一个“中心”，然后向两边扩展判断是否相同。
• 回文串长度可能是奇数或偶数：
  • 奇数长度：中心是一个字符，如 "aba"，中心是 'b'。
  • 偶数长度：中心是两个相同字符，如 "abba"，中心是 "bb"。

思路：

• 遍历字符串的每个位置，把它当作可能的回文中心。
• 对每个中心，向左右扩展，直到左右字符不相等为止，记录此时的回文长度。
• 比较所有中心扩展得到的回文，取最长的一个。

复杂度：

• 有 n 个可能的单字符中心，n-1 个双字符中心，总共 2n-1 个中心。
• 每个中心扩展最多 O(n) 时间。
• 总复杂度 O(n²)，空间 O(1)。

4. 逐步推导

以 s = "babad" 为例：

步骤 1：定义辅助函数
我们可以写一个函数 expandAroundCenter(left, right)，从 left 和 right 开始向两边扩展，返回回文长度和子串。

步骤 2：遍历中心

• i=0，中心是 'b'（奇数扩展）：
  • 初始 left=0, right=0，扩展：左右都是 0，回文 "b"，长度 1。
• i=0，中心是 "bb"? 不对，偶数中心是 (0,1) 即 "ba" 吗？不相等，所以偶数扩展长度为 0。
• 继续 i=1：
  • 奇数中心 'a'：左右扩展，比较 s[0] 和 s[2]：'b' 和 'b' 相等，再比较 s[-1] 越界停止，得到 "bab"，长度 3。
  • 偶数中心 (1,2) 'ba'？不相等，扩展长度为 0。
• i=2：
  • 奇数中心 'b'：扩展比较 s[1] 和 s[3]：'a' 和 'a' 相等，再比较 s[0] 和 s[4]：'b' 和 'd' 不等，得到 "aba"？不对，仔细看：
    初始 left=2, right=2，扩展：left=1, right=3 → 'a'='a'，再 left=0, right=4 → 'b'≠'d'，所以回文是 s[1:4] 即 "aba"，长度 3。
  • 偶数中心 (2,3) 'ad' 不相等，扩展长度为 0。
• 继续直到结束，记录最长回文。

最终最长是 "bab" 或 "aba"，长度 3。

5. 代码实现（Python）

def longestPalindrome(s: str) -> str:
    def expandAroundCenter(left, right):
        # 从中心向两边扩展，直到不是回文
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        # 返回回文子串（注意最后多扩展了一次，所以要回退）
        return s[left + 1:right]
    
    res = ""
    for i in range(len(s)):
        # 奇数长度回文，中心 i
        odd = expandAroundCenter(i, i)
        # 偶数长度回文，中心 i 和 i+1
        even = expandAroundCenter(i, i + 1)
        
        # 更新最长回文
        if len(odd) > len(res):
            res = odd
        if len(even) > len(res):
            res = even
    return res

6. 复杂度分析

• 时间复杂度：O(n²)，因为每个中心扩展最多可能需要 O(n) 时间。
• 空间复杂度：O(1)（除了存储结果外，没有使用额外空间）。

7. 更优算法（了解即可）

还有一个 Manacher 算法 可以在 O(n) 时间内解决此问题，但实现较复杂，面试中一般掌握中心扩展法即可。

8. 总结

• 回文串问题常利用中心扩展来降低复杂度。
• 注意奇偶两种情况都要考虑。
• 中心扩展法直观且易于实现，是面试中的常见解法。

这样讲解是否清晰？需要我进一步解释某一部分吗？