最长回文子串
Longest Palindromic Substring
求字符串中最长的回文子串；子串必须连续。
在力扣中练习题目描述
给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
解题思路
区间 DP · 首尾向内
首尾字符相同，且内部子串是回文，整体才是回文
暴力枚举所有子串、再逐段判断回文是 O(n³)。用 dp[i][j] 表示 s[i..j] 是否为回文，就能把判断压成一次转移：
dp[i][j] = (s[i] == s[j]) && (j - i < 2 || dp[i+1][j-1])
也就是说：首尾字符必须相同；长度不超过 2 时直接成立，更长时还要看内部区间。
自拟主例 s = "abac"。长度 2 的区间首尾都不同，全部为 F；长度 3 的 "aba" 首尾都是 a，内部 "b" 是回文，于是成立；长度 4 的 "abac" 首尾 b/c 不同，直接失败。
dp[i][j]：s[i..j] 是否为回文；按区间长度从小到大填表，内部区间先确定
dp[2][3]=F填表顺序必须按区间长度从小到大：计算长度 L 时，内部长度 L-2 的区间已经确定。如果按 i、j 双重循环随便填，dp[i+1][j-1] 可能还没算。
"aba" 首尾都是 'a'，内部 "b" 也是回文，所以是回文；当前最长 aba。
- L
- 3
- 最长
- aba
dp[i][j]：s[i..j] 是否为回文；按区间长度从小到大填表，内部区间先确定
dp[0][2]=dp[1][1]T=T边界是对角线 dp[i][i] = true。答案在填表过程中用 start/len 记录，时间 O(n²)，空间 O(n²)。
易错点
- 按 i、j 从小到大填表：dp[i+1][j-1] 还没计算，内部区间读到默认 false。
- 长度 2 也去读 dp[i+1][j-1]：此时内部是空区间，i+1 > j-1，需要单独处理。
- 首尾相同时直接返回 true：内部区间可能并不是回文，必须继续检查 dp[i+1][j-1]。
中心扩展 · O(1) 空间
回文从中心向两边对称，枚举中心即可
时间同为 O(n²)，但只用了常数空间，也不需要维护二维表；代价是每次扩展可能重复扫描同一段字符。
回文串关于中心对称。中心有两种：
- 奇数长度：中心是一个字符，例如
"bab"的中心是a； - 偶数长度：中心是两个字符之间的空隙，例如
"abba"的中心在两个 b 之间。
对每个中心向左右扩展，直到字符不同或越界，就得到以它为中心的最长回文。共有 2n-1 个中心，每个中心最多扩展 O(n)，总时间 O(n²)，空间 O(1)。
实现时用 expand(i, i) 处理奇数中心，expand(i, i+1) 处理偶数中心。扩展结束后，r - l - 1 就是回文长度，起点是 l + 1。
- 1start = 0，len = 1。
- 2对每个 i，分别调用 expand(i, i) 和 expand(i, i+1)。
- 3向两边扩展直到字符不同或越界。
- 4长度更大时更新 start/len。
- 5返回 s.substr(start, len)。
易错点
- 只扩展奇数中心：偶数长度的回文会被漏掉。
- 扩展结束后起点写成 l：循环退出时 l 已经多减了 1，起点应为 l+1。
- 长度相同也更新：会改变先找到的答案，虽然仍是正确回文，但结果不稳定。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
s = "abac"单个字符都是回文：对角线全部设为 true，长度 1。
- s
- abac
dp[i][j]：s[i..j] 是否为回文；按区间长度从小到大填表，内部区间先确定
dp[0][0]=T查看 C++ 代码
延伸阅读
- 区间 DP 的填表顺序由依赖方向决定：依赖更短区间，就按长度递增。
- 最长回文子序列（516）不要求连续，状态定义相似，但转移在首尾不同时取两边的最大值。