如何统计字符串中回文子串的数目？（LeetCode 647）

简化版

统计字符串 s 中回文子串的个数（每个不同的起止位置算一个，即使内容相同也分别计数，如 "aaa" 有 6 个）。和「最长回文子串」同源，用中心扩展法：枚举 2n-1 个中心（单字符 + 字符间隙），每个中心向两边扩展，每成功扩展一次（两边字符相等）就是一个新的回文子串，计数 +1。O(n²) 时间、O(1) 空间。

详细版

int countSubstrings(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        count += expand(s, i, i);       // 奇数长度回文（单字符中心）
        count += expand(s, i, i + 1);   // 偶数长度回文（间隙中心）
    }
    return count;
}

// 从中心向两边扩展，返回以此中心的回文子串个数
int expand(String s, int left, int right) {
    int cnt = 0;
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        cnt++;          // 每次两边相等，就找到一个回文子串
        left--; right++;
    }
    return cnt;
}

和最长回文子串的区别：那题记录最长长度，本题每扩展成功一次就 +1（每一层扩展都是一个独立的回文子串）。
两类中心：单字符（奇回文）+ 字符间隙（偶回文），共 2n-1 个。
复杂度：O(n²) 时间、O(1) 空间。

完整版教学

一、题意：计数而非求最长

本题和最长回文子串（5）是「一体两面」——都基于「回文关于中心对称」，都用中心扩展。区别在于输出：

最长回文子串：只关心最长的那一个，记录最大长度和边界。
回文子串数目（本题）：要数出所有回文子串的个数，每个不同位置的回文都算，哪怕内容一样。例如 "aaa"：单字符 a、a、a（3 个），双字符 aa、aa（2 个），三字符 aaa（1 个），共 6 个。

二、中心扩展 + 计数

沿用中心扩展框架，枚举 2n-1 个中心（每个字符、每个字符间隙）。关键改动在扩展函数：每当向两边扩展一次且两端字符相等，就意味着发现了一个以当前中心的、更长一圈的回文子串，count++。

为什么每扩一层就是一个新回文？以中心 i 为例：

第一次判断 s[i]==s[i]（自己和自己）成立 → "a" 是一个回文，+1。
扩到 s[i-1]==s[i+1] 成立 → "aba" 是一个回文，+1。
再扩 s[i-2]==s[i+2] 成立 → 更长的回文，+1。
直到不相等或越界停止。

每一层成功扩展 = 一个独立的回文子串，累加即总数。

三、为什么两类中心不重复计数

单字符中心 expand(i, i) 数的是奇数长度回文（"a", "aba", "ababa"…）。
间隙中心 expand(i, i+1) 数的是偶数长度回文（"aa", "abba"…）。

奇数长度和偶数长度的回文互不重叠（一个回文串长度要么奇要么偶，只会被对应类型的中心数到一次），所以两类相加不会重复也不会遗漏，恰好覆盖所有回文子串。

四、其他解法

动态规划 O(n²)：dp[i][j] 表示 s[i..j] 是否回文，dp[i][j] = s[i]==s[j] && (j-i<2 || dp[i+1][j-1])，统计所有为 true 的 (i,j)。时间同中心扩展，但要 O(n²) 空间。
Manacher O(n)：把每个中心的最大回文半径求出来，sum(半径的相关量) 即回文子串总数。是本题的最优解，但实现复杂，加分项。

面试用中心扩展（O(n²)、O(1) 空间）最平衡。

五、易错点

和最长回文混淆：本题是累加每一层（cnt++ 在 while 内、每次相等都加），不是记录最长长度。
漏偶数中心：必须两种中心都枚举，否则漏掉所有偶数长度回文。
计数含义：不同位置算不同回文（"aaa" 的两个 "aa" 分别计），不是去重后的「不同回文串种类数」。若题目要「不同的回文子串种类」则要用回文树/后缀结构，那是另一道题。

六、扩展一次就对应一个唯一子串

统计题不能只记录每个中心的最长半径；从某中心每成功扩展一层，就新得到一个端点唯一的回文子串，应立即 count++。同一子串只有一个几何中心，因此奇偶中心枚举不会重复计数。

s="aaa"，共有 5 个中心
中心 (0,0)："a" -> 1 个
中心 (0,1)："aa" -> 1 个
中心 (1,1)："a"、"aaa" -> 2 个
中心 (1,2)："aa" -> 1 个
中心 (2,2)："a" -> 1 个
总数 1+1+2+1+1=6

校验维度	本题必须保持的结论
循环/递推不变量	每次左右字符相等并未越界时，当前 `[l,r]` 是新发现且尚未计数的唯一回文子串。
边界条件	相同文本出现在不同位置算不同子串；空串计数为 0。
复杂度与代价	最坏 O(n²) 次成功/失败比较，额外空间 O(1)；DP 需要 O(n²) 空间。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

字符串题首先要固定“处理的是字符、UTF-16 代码单元还是 Unicode 码点”，再讨论下标与窗口。本题应先复述这条不变量：每次左右字符相等并未越界时，当前 [l,r] 是新发现且尚未计数的唯一回文子串。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“s=“aaa”，共有 5 个中心”开始手推，最后应得到“总数 1+1+2+1+1=6”。
边界复核：相同文本出现在不同位置算不同子串；空串计数为 0。
代价复核：最坏 O(n²) 次成功/失败比较，额外空间 O(1)；DP 需要 O(n²) 空间。
用空串、单字符、全相同字符和首尾命中检查下标边界。
涉及窗口或双指针时，明确区间是闭区间还是左闭右开，并在移动后再判断长度。
涉及计数数组时，先确认题目字符集；超出小写英文字母就不能硬套 26 个桶。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“每次左右字符相等并未越界时，当前 [l,r] 是新发现且尚未计数的唯一回文子串。”这条正确性主线不能省。

八、常见误区与追问

误区：只统计不同内容的回文字符串。 题目按起止位置计数，aaa 中三个单字符 a 是三个子串。
误区：每个中心只贡献一个回文。 一个中心可能逐层产生多个回文，如中心 a 可产生 a、aaa。
误区：奇偶中心会重复统计同一子串。 一个固定区间的中心唯一，长度奇偶决定它属于哪一类中心。
追问：与最长回文子串的代码差异是什么？ 扩展框架相同，但本题每次成功都累加，最长题只维护最大区间。
追问：DP 如何计数？ 当 s[l]==s[r] 且内部为空、单字符或已回文时令状态真并累加。
追问：最坏情况是什么？ 所有字符相同会让几乎每个中心扩到边界，产生 n(n+1)/2 个回文。

九、加强记忆

回文子串数目 = 中心扩展 + 逐层计数。和最长回文子串同框架（枚举 2n-1 个中心：单字符=奇回文、间隙=偶回文），区别是每向两边成功扩展一次（两端相等）就 count++——每一层扩展是一个独立回文子串。奇/偶两类中心覆盖所有回文、不重不漏。"aaa" = 6 个（按位置计，不去重）。O(n²) 时间 O(1) 空间；最优 Manacher O(n)。核心：从每个中心往外撑，撑成功几层就有几个回文。

简化版

详细版