题目描述
找出字符串里最长的回文子串(连续)。
思路解析
最直接的笨办法：枚举起点和终点(n² 个子串)，每个子串再花 O(n) 判断是否回文，合起来 O(n³)。换个思路：回文一定有个中心，从中心往两边扩，能省一个量级。
为什么成立：回文关于中心镜像对称，知道中心就能向外验证。对每个中心，l、r 一起向外走，只要 s[l]==s[r] 就继续扩；一旦不等或越界就停。中心有两种——单字符(奇回文)和两字符之间(偶回文)，都试一遍取最长。
奇中心 · 以下标 1 的 a 出发：从中心 a(下标 1)开始，l=r=1。单字符本身就是回文，作为起点向两边扩。
向外扩 · s[0]==s[2] ✓：l 退到 0(b)、r 进到 2(b)，s[0]==s[2]，扩成功！当前回文 "bab"、长度 3，刷新最长记录。继续往外扩。
再扩 · l 越界，停：转折：l 再退一步就到 −1 越界，扩展终止。以 a 为奇中心扩出的最长回文是 "bab"(长度 3)。换下一个中心。
偶中心 · 下标 0、1 之间(负例)：试偶中心(下标 0、1 之间)：l=0 是 b、r=1 是 a，s[0]≠s[1]，第一步就不相等，一次都没扩成，这个偶中心贡献长度 0。这就是负例：不等立刻停。
奇中心 · 以下标 2 的 b 出发：再换中心：以下标 2 的 b 为奇中心，l=r=2，单字符回文起步，向两边扩。
向外扩 · s[1]==s[3] ✓：l 退到 1(a)、r 进到 3(a)，s[1]==s[3]，扩成功！回文 "aba"、长度 3，和当前最长打平。继续扩。
再扩 · s[0]≠s[4]，停(负例)：继续扩到 l=0(b)、r=4(d)，s[0]≠s[4]，不相等，扩展停止。以 b 为中心扩出的最长仍是 "aba"(长度 3)。
所有中心扫完 · 最长长度 3：把每个奇中心、偶中心都扩一遍：最长是 "bab" 和 "aba"，长度都为 3。返回其一即可。
抓住"回文关于中心对称"这一点，就把"枚举子串 + 判回文"两件事并成一件：从中心往外扩，扩到哪算到哪。回文子串计数(647)、最长回文子序列(516)都和它同源。
参考代码（Python）
1n = len(s)
2def expand(l, r): # 从中心向两边扩
3 while l >= 0 and r < n and s[l] == s[r]: # 两端相等才继续
4 l -= 1; r += 1
5 return l + 1, r - 1 # 退出时各多走一步，收回一格
6best = (0, 0)
7for i in range(n):
8 for a, b in (expand(i, i), expand(i, i + 1)): # 奇 + 偶 两种中心
9 if b - a > best[1] - best[0]: best = (a, b)
10return s[best[0]:best[1] + 1]复杂度分析
- 时间复杂度：O(n²) —— n 个中心 × 每个中心最多扩 n/2 步
- 空间复杂度：O(1) —— 只用 l、r 几个指针
套路模板
记住骨架：一个 expand 函数、每个位置试奇偶两种中心、相等就向外扩。把"记录最长"换成"累加扩成功次数"就是回文子串计数(647)。
1def expand(l, r):
2 while l >= 0 and r < n and s[l] == s[r]: # 两边相等就扩
3 l -= 1; r += 1
4 return r - l - 1 # 此中心的回文长度
5for i in range(n):
6 odd = expand(i, i) # 奇中心: 单字符
7 even = expand(i, i + 1) # 偶中心: 两字符之间易错点
- 错误写法：只试奇数长度中心 (i,i) → 正确写法：奇 (i,i) 和偶 (i,i+1) 两种都要试（"abba" 这类偶回文中心落在两字符之间，只试奇中心会漏掉）
- 错误写法：退出后直接用 l、r 当区间 → 正确写法：while 停后回文是 [l+1, r-1]（循环退出时 l、r 已各多走一步、踩到不等或越界处）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。