LeetCode LCR 020. 回文子串
目录
题目描述
题意分析
给定一个字符串，统计其中回文子串的数目。子串是连续的一段字符，而不是子序列。
这里的「不同」是按位置区分而非按内容区分：只要起止下标不同就算作两个不同的子串，哪怕它们的字符完全一样。这一点直接决定了答案的量级——
"aaa"里三个单独的a要计三次，答案是 6 而不是去重后的 3。
约束信号在于字符串长度上限只有 1000 量级，这意味着 $O(n^2)$ 的时间是被允许的，不必去追求线性算法；同时也提醒 $O(n^2)$ 的额外空间虽然勉强能过，但如果能做到 $O(1)$ 空间会更好。
边界要点：长度为 1 的子串一定是回文，所以答案至少是 $n$；长度为 2 的子串是回文当且仅当两个字符相同；字符串本身可能整体就是回文；全部字符相同时回文子串数量达到最大值 $n(n+1)/2$。
解法：中心扩展
核心思路
最朴素的做法是枚举所有 $O(n^2)$ 个子串，再对每个子串用双指针花 $O(n)$ 判断是否回文，总共 $O(n^3)$。
瓶颈在于每个子串的回文判断都是从零开始的，完全没有利用已经算过的结果。观察回文的递归结构：
s[l..r]是回文，当且仅当s[l] == s[r]且s[l+1..r-1]是回文。这条性质有两种用法。一种是自底向上填表，按子串长度从小到大做区间 dp，用一张二维布尔表记住每个区间是否回文，时间降到 $O(n^2)$，但要付出 $O(n^2)$ 的空间。另一种是反过来用：把这条性质从内向外读——既然回文一定是从它的中心一层层向外「长」出来的，那就直接枚举中心，向两侧同时扩展，只要两端字符相等就多得到一个回文子串，一旦不等就可以立刻停止，因为再往外扩必然不是回文。后者时间同样是 $O(n^2)$，却只需要 $O(1)$ 空间。
采用中心扩展就必须回答一个问题：枚举哪些中心才不重不漏？关键在于回文的中心不一定是一个字符。长度为奇数的回文，中心是正中间那个字符，共有 $n$ 种取法；长度为偶数的回文，中心落在两个相邻字符的缝隙上，共有 $n-1$ 种取法。两者相加，一共 $2n-1$ 个中心，这个集合是完备的：任何一个回文子串
s[l..r]，无论长度奇偶，它的中心 $(l+r)/2$ 都唯一地落在这 $2n-1$ 个位置中的某一个上；反过来，同一个中心扩展出的不同层数对应不同长度的回文，也不会与别的中心产生重复。于是「枚举回文子串」与「枚举中心 × 扩展层数」是一一对应的。
由此得到不变量：对固定中心的一次扩展循环，每成功匹配一层，就恰好对应一个以该中心为中心的回文子串，且这些子串两两不同；因此把所有中心的成功扩展次数加起来，就是答案的精确值。
解题步骤
- 把答案初始化为 0，然后遍历每个下标
center。遍历下标是为了同时枚举以它为中心的奇数回文、以及以它和它右邻字符之间的缝隙为中心的偶数回文，两类合起来正好覆盖全部 $2n-1$ 个中心。- 对每个下标调用一次扩展，左右指针都设为
center。这对应奇数长度的回文，初始那一层就是单个字符本身，必然匹配成功，所以每个下标至少贡献 1。- 再调用一次扩展，左指针为
center、右指针为center + 1。这对应偶数长度的回文；当center是最后一个下标时右指针越界，扩展函数的边界判断会让它直接返回 0，因此不需要额外特判。- 扩展函数里，只要左指针不越左界、右指针不越右界、且两端字符相等，就把计数加一，然后左指针左移、右指针右移继续。加一是因为当前这一层本身就构成一个新的回文子串；一旦条件不满足立刻退出循环，因为外层不匹配时，更外层的子串必然也不是回文，不存在漏掉更长回文的可能。
- 把两次扩展的返回值累加到答案上，遍历结束后返回答案。
以
"aaa"走一遍（$n = 3$，共 $2 \times 3 - 1 = 5$ 个有效中心）：center = 0时，奇数扩展从(0, 0)开始，s[0] == s[0]计 1，随后左指针变为 -1 越界停止，贡献 1（子串a）；偶数扩展从(0, 1)开始，s[0] == s[1]计 1，再往外左指针越界停止，贡献 1（子串aa）。center = 1时，奇数扩展从(1, 1)计 1，再扩到(0, 2)，s[0] == s[2]再计 1，然后左指针越界停止，贡献 2（子串a、aaa）；偶数扩展从(1, 2)计 1，再扩到(0, 3)时右指针越界停止，贡献 1（子串aa）。center = 2时，奇数扩展从(2, 2)计 1，再扩右指针越界，贡献 1（子串a）；偶数扩展从(2, 3)起右指针已越界，贡献 0。累加得 $1 + 1 + 2 + 1 + 1 + 0 = 6$。逐个列出验证：三个单字符a、两个aa、一个aaa，恰好 6 个，与 $n(n+1)/2 = 6$ 吻合。
代码实现
class Solution {
public int countSubstrings(String s) {
int ans = 0;
for (int center = 0; center < s.length(); center++) {
ans += expand(s, center, center);
ans += expand(s, center, center + 1);
}
return ans;
}
private int expand(String s, int left, int right) {
int count = 0;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
// 每扩展成功一次，就对应一个新的回文子串。
count++;
left--;
right++;
}
return count;
}
}
func countSubstrings(s string) int {
ans := 0
for center := 0; center < len(s); center++ {
ans += expandPalindrome(s, center, center)
ans += expandPalindrome(s, center, center+1)
}
return ans
}
func expandPalindrome(s string, left int, right int) int {
count := 0
for left >= 0 && right < len(s) && s[left] == s[right] {
// 奇偶中心都通过同一个扩展函数统计。
count++
left--
right++
}
return count
}
复杂度分析
- 时间复杂度：$O(n^2)$，一共枚举 $2n - 1$ 个中心，每个中心向外扩展的层数不超过 $\lceil n/2 \rceil$，每层只做一次字符比较，因此上界是 $2n - 1$ 与 $n$ 的乘积同阶。全部字符相同时能取到这个上界。
- 空间复杂度：$O(1)$，只用了答案、计数以及左右两个指针，没有额外开辟与 $n$ 相关的结构；相比之下区间 dp 解法需要 $O(n^2)$ 的布尔表。
关键点总结
- 统计类问题的第一步是明确「不同」的判定标准。本题按位置区分而非按内容去重，确定了这一点，
"aaa"的答案是 6 还是 3 才有定论，整个算法的形态也随之确定。- 回文的递归结构可以正着用也可以反着用。自底向上填表得到区间 dp，从内向外生长得到中心扩展；两者时间同阶，但后者省掉了整张二维表，是典型的「换个方向读同一条递推式，就省下一维空间」。
- 枚举时必须论证枚举集合的完备性。$2n - 1$ 个中心不重不漏地覆盖了所有回文子串，这个论证比代码本身更重要，也是遗漏偶数中心这个高频错误的根源。
- 剪枝的依据要说得出来。扩展一旦失配就能立刻停止，是因为外层不匹配时更外层必然也不是回文，这不是经验而是回文定义的直接推论。
- 面试视角：本题常与 5 题（最长回文子串）连着问，两者的中心扩展骨架完全一致，差别只在扩展成功时做什么——本题是「计数加一」，5 题是「更新最长区间的左右端点」。能主动点出这层关系并顺手说明「统计个数不需要记录区间、因此空间可以降到 $O(1)$」，通常比只写出代码更加分。若被追问更优解，方向是 Manacher 算法，它能把时间降到 $O(n)$，同时天然统一奇偶中心。
易错点总结
- 错误写法：只枚举
(i, i)这一类中心，漏掉(i, i + 1)。用例"aaa"→ 只统计到奇数长度的a、a、a、aaa共 4 个，漏掉两个aa，输出 4 而非 6。- 错误写法：把「回文子串」按内容去重。用例
"aaa"→ 只算出a、aa、aaa三种不同内容，输出 3。题目要的是位置不同即算不同。- 错误写法：套用最长回文子串的模板，扩展时只更新最大长度而不累加计数。用例
"aaa"→ 得到最长回文长度 3，但答案要求的是数量 6，这是把 647 和 5 两道题混为一谈的典型表现。- 错误写法：扩展循环里先比较字符再判断边界，或者干脆不判边界。用例
"aaa"→ 从(1, 1)扩到(0, 2)成功后继续扩到(-1, 3)，下标为 -1 时字符访问越界报错。边界检查必须写在字符比较之前，靠短路求值挡住越界。- 错误写法：扩展中途遇到失配不退出，只是跳过这一层继续往外试。用例
"axbya"→ 以下标 2 为中心时，第二层s[1] = x与s[3] = y失配本应终止，若继续扩到第三层会发现s[0] = a与s[4] = a相等，于是把整串误计为回文，输出 6 而正确答案是 5（只有五个单字符）。失配即终止是这个解法成立的前提。- 错误写法：只在扩展结束后按最终跨度算一次贡献，而不是每成功一层加一次。用例
"aaa"→ 中心为下标 1 的那次扩展成功了两层，只记一次就漏掉了a或aaa中的一个，总数偏小。每一层都是一个独立的回文子串。- 错误写法：担心偶数扩展的右指针越界，把外层循环上界写成
center < s.length() - 1。用例"a"→ 循环体一次都不执行，输出 0，正确答案是 1；用例"aaa"→ 最后一个下标的奇数中心被一并丢掉，输出 5 而非 6。越界应由扩展函数内部的边界判断兜住，而不是砍掉外层循环。- 错误写法：改用区间 dp 时按下标
i从小到大、j从小到大的顺序填表。用例"aaa"→ 计算dp[0][2]时依赖的dp[1][1]还未被填写，读到默认值导致漏计。区间 dp 必须按区间长度递增或让左端点倒序遍历。- 错误写法：把子串当成子序列来统计。用例
"abcba"→ 下标 0、2、4 组成的aca是回文子序列但不是子串，一旦计入答案就会偏大。本题的子串必须是连续的一段。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 5. 最长回文子串 | 中等 | 同一套中心扩展，扩展成功时记录区间而非计数 |
| 516. 最长回文子序列 | 中等 | 对象是子序列，不连续因而无中心可扩，只能 dp |
| 131. 分割回文串 | 中等 | 回文判定只是子过程，主体是回溯枚举所有分割 |
| 214. 最短回文串 | 困难 | 求最长回文前缀，需借助 KMP 的前缀函数做到线性 |