好的，这次我们选择 LeetCode 第 5 题「最长回文子串」。
这道题是字符串处理中的经典题目，既考察对回文特性的把握，也涉及不同的算法优化思路。

1. 题目描述

题目：
给定一个字符串 s，找到 s 中最长的回文子串。
如果存在多个最长回文子串，返回任意一个即可。

示例：

输入: s = "babad"
输出: "bab" 或 "aba"

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

注意：

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

2. 理解回文串与题意

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

子串：字符串中连续的一段。
注意和“子序列”不同，子序列可以不连续，但子串必须连续。

难点：

• 字符串长度最大 1000，不能暴力枚举所有子串并检查（那样是 O(n³) 或 O(n²) 检查 × O(n) 比较，会超时）。
• 需要找到 O(n²) 或更优的算法。

3. 思路 1：中心扩散法（直观解法）

3.1 核心思想

回文串有两种形式：

1. 奇数长度：如 "aba"，中心是一个字符。
2. 偶数长度：如 "abba"，中心是两个相同字符。

我们可以枚举每一个可能的“中心”，然后向两边扩展，直到不再构成回文为止。

3.2 算法步骤

1. 遍历字符串的每个位置 i，考虑两种情况：
   • 以 s[i] 为中心（奇数长度）
   • 以 s[i] 和 s[i+1] 为中心（偶数长度，需保证 s[i] == s[i+1]）
2. 对每个中心，用两个指针 left 和 right 向两边扩展，比较 s[left] 和 s[right] 是否相等。
3. 记录扩展过程中遇到的最长回文子串的起始位置和长度。

3.3 举例说明

以 s = "babad" 为例：

• i = 0，奇数扩展：中心 "b"，左右都是 b，扩展后 "b"，长度 1。
• i = 0，偶数扩展：比较 s[0] 和 s[1] (b 和 a) 不同，不扩展。
• i = 1，奇数扩展：中心 "a"，左右 b 和 b 相同 → "bab"，再往外 a 和 d 不同，停止，长度 3。
• i = 1，偶数扩展：比较 s[1] 和 s[2] (a 和 b) 不同，不扩展。
• i = 2，奇数扩展：中心 "a"，左右 b 和 d 不同 → "a"，长度 1。
• i = 2，偶数扩展：比较 s[2] 和 s[3] (a 和 b) 不同，不扩展。
• i = 3，奇数扩展：中心 "b"，左右 a 和 d 不同 → "b"。
• i = 3，偶数扩展：比较 s[3] 和 s[4] (b 和 d) 不同，不扩展。

最长是 "bab"（或 "aba" 在另一种中心扩展时得到）。

4. 思路 2：动态规划（填表法）

4.1 核心思想

定义 dp[i][j] 表示子串 s[i..j] 是否为回文串。
转移方程：

• 如果 s[i] == s[j]，并且 j - i <= 2 或者 dp[i+1][j-1] 是回文，那么 dp[i][j] = true。
• 否则为 false。

解释：

• 当子串长度 1 (i == j)：肯定是回文。
• 长度 2 (j == i+1)：两个字符相同就是回文。
• 长度大于 2：两头字符相同，并且中间子串是回文，整体才是回文。

4.2 算法步骤

1. 初始化一个二维数组 dp，大小 n x n，初始 false。
2. 所有长度为 1 的子串都是回文：dp[i][i] = true。
3. 按子串长度 len 从 2 到 n 遍历：
   • 遍历起始位置 i，计算 j = i + len - 1，如果 j >= n 则跳过。
   • 根据上述规则填 dp[i][j]。
4. 记录为 true 且长度最大的子串的起始和长度。

4.3 复杂度

• 时间 O(n²)
• 空间 O(n²)

5. 代码实现（中心扩散法，因为更常用且空间优）

这里给出中心扩散法的 Python 实现：

def longestPalindrome(s: str) -> str:
    n = len(s)
    if n < 2:
        return s
    
    def expandAroundCenter(left, right):
        # 从中心向两边扩展，返回回文长度
        while left >= 0 and right < n and s[left] == s[right]:
            left -= 1
            right += 1
        # 循环结束时，左右多扩了一次，实际回文区间 [left+1, right-1]
        return right - left - 1
    
    start, max_len = 0, 1
    for i in range(n):
        len1 = expandAroundCenter(i, i)      # 奇数长度
        len2 = expandAroundCenter(i, i + 1)  # 偶数长度
        cur_len = max(len1, len2)
        if cur_len > max_len:
            max_len = cur_len
            # 计算起始位置：i 是中心，回文长度 cur_len，则 start = i - (cur_len - 1) // 2
            start = i - (cur_len - 1) // 2
    return s[start:start + max_len]

6. 复杂度分析（中心扩散法）

• 时间：O(n²) — 每个中心最多扩展 O(n) 次，共有 2n−1 个中心（n 个单字符中心 + n−1 个双字符中心），但每个中心扩展的总次数不超过 n，所以是 O(n²)。
• 空间：O(1) — 只用了常数个变量。

7. 更优算法（Manacher 算法）简介

还有一个 O(n) 时间复杂度的算法叫 Manacher 算法，利用回文对称性避免重复计算。
它很高效，但实现较复杂，面试中一般掌握中心扩散法和动态规划即可。

这样循序渐进地讲解，你理解了吗？如果有哪一步不清楚，我可以再详细解释。