最长回文子串的变种——统计不同回文子串的个数（进阶版：统计长度至少为L的不同回文子串个数）

题目描述

给定一个字符串 s，需要统计其中不同（distinct）回文子串的个数。
进阶要求：只统计长度至少为 L 的不同回文子串个数。

例如：

• 输入 s = "abc"，长度为 1 的子串 "a"、"b"、"c" 都是回文，但它们是不同的，共有 3 个。长度至少为 2 的没有，所以是 0。
• 输入 s = "aaa"，长度为 1 的回文子串是 "a"（只算一个，因为不同子串去重），长度为 2 的回文子串是 "aa"，长度为 3 的是 "aaa"，但 "aa" 在长度为 2 中出现一次，在长度为 3 中会重复出现（子串 "aa" 可以是 s[0:2] 或 s[1:3]，但作为不同子串时，内容相同的 "aa" 只算一个），所以最终不同回文子串是 {"a", "aa", "aaa"} 共 3 个。如果 L=2，则答案是 2。

注意：子串是连续的，不是子序列。不同子串去重是按字符串内容，不是按位置。
目标：时间复杂度尽量低（O(n²) 可接受，n ≤ 2000 常见）。

解题思路

本题是经典“最长回文子串”问题的变种。
最长回文子串通常有两种常用方法：中心扩展法 和 动态规划法。
对于统计不同回文子串，中心扩展法更容易去重，但需要记录已找到的子串，用哈希集合存储。
进阶要求 L ≥ 1 时，只需在保存时判断长度是否 ≥ L。

但为了讲解动态规划思路，下面我用动态规划来做，并说明如何统计去重。

1. 动态规划状态定义

设

\[dp[i][j] \quad 表示子串\ s[i..j]\ 是否是回文串，值为\ true/false \]

其中 i ≤ j。

2. 状态转移方程

• 基本情况：
  1. 单个字符是回文：dp[i][i] = true
  2. 两个字符相同是回文：dp[i][i+1] = (s[i] == s[i+1])
• 扩展：
  对于长度大于 2 的子串：

\[ dp[i][j] = dp[i+1][j-1] \ \&\&\ s[i] == s[j] \]

也就是说，如果 s[i] 和 s[j] 相同，且中间的子串是回文，则整体是回文。

3. 计算顺序

按子串长度从小到大计算：

• 长度 len = 1 → 直接填 true
• 长度 len = 2 → 判断相邻字符是否相同
• 长度 len 从 3 到 n → 利用长度 len-2 的结果

这样可以保证 dp[i+1][j-1] 已经被计算过。

4. 统计不同回文子串

在 dp[i][j] = true 时，子串 s[i..j] 是一个回文子串，把它加入集合（比如哈希集合 unordered_set 或 set）。
但这样需要提取子串，在动态规划过程中提取会带来 O(n) 的子串构造代价，总复杂度 O(n³) 会超时。
优化：不实际存储子串内容，而存储子串的哈希值（如双哈希或直接转成 (i, j) 对，但注意去重要按内容）。
因此另一种简单做法是不依赖动态规划集合，而用回文自动机（Palindromic Tree）来统计，但这里我们先用动态规划+集合实现，便于理解。

5. 去重处理

去重必须按子串内容。我们可以在 dp 计算时，对于 dp[i][j] = true 的，将其内容 s[i..j] 加入集合。
但为了优化，我们可以用字符串哈希（如滚动哈希）预处理字符串的哈希值，这样可以在 O(1) 得到子串的哈希值，用哈希值来去重。
但哈希值有碰撞风险，为简单讲解，这里假设我们用 64 位无符号整数滚动哈希，冲突概率很低，可接受。

6. 进阶：长度至少为 L

在加入集合之前判断 j-i+1 >= L 即可。

7. 详细步骤

步骤 1：预处理字符串哈希

使用多项式滚动哈希，对字符串 s 预处理前缀哈希值，以及对应的幂次数组，用于 O(1) 计算子串哈希值。

步骤 2：动态规划填表

初始化 n × n 的二维布尔数组 dp 为 false。
遍历长度 len 从 1 到 n：

• 对于每个起始位置 i，计算 j = i + len - 1
• 如果 len == 1: dp[i][i] = true
• 如果 len == 2: dp[i][j] = (s[i] == s[j])
• 否则: dp[i][j] = dp[i+1][j-1] && (s[i] == s[j])
• 如果 dp[i][j] 为 true 且长度 len >= L：
  • 计算子串哈希值（或直接用子串内容），加入集合

步骤 3：统计结果

最终集合的大小就是不同回文子串的个数。

8. 时间复杂度

• 动态规划 O(n²)
• 每次计算哈希 O(1)（如果已预处理）
• 总体 O(n²)，可接受 n ≤ 5000
• 去重集合插入哈希值 O(1) 平均，总 O(n²) 时间，空间 O(n²) 用于 dp 矩阵，但可用滚动数组优化空间为 O(n) 不过不影响集合数量。

9. 例子演示

s = "ababa", L = 2

1. 长度 1 的回文子串：a, b （但长度 1 不满足 L≥2，所以不加入集合）
2. 长度 2 的：ab, ba, ab, ba 都不是回文，dp=false
3. 长度 3 的：aba（是），bab（是），aba（是但重复）
   集合得到 {"aba", "bab"}
4. 长度 4 的：abab（否），baba（否）
5. 长度 5 的：ababa（是）加入集合 {"aba", "bab", "ababa"}

结果集合大小 = 3。

10. 代码框架（C++风格伪代码）

int countDistinctPalindromicSubstrings(string s, int L) {
    int n = s.length();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    unordered_set<unsigned long long> seen; // 假设用 64 位哈希值
    
    // 预处理滚动哈希
    const int base = 131;
    vector<unsigned long long> hash(n+1, 0), pow(n+1, 1);
    for (int i = 0; i < n; i++) {
        hash[i+1] = hash[i] * base + (s[i] - 'a' + 1);
        pow[i+1] = pow[i] * base;
    }
    auto getHash = [&](int l, int r) -> unsigned long long {
        return hash[r+1] - hash[l] * pow[r-l+1];
    };
    
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (len == 1) {
                dp[i][j] = true;
            } else if (len == 2) {
                dp[i][j] = (s[i] == s[j]);
            } else {
                dp[i][j] = dp[i+1][j-1] && (s[i] == s[j]);
            }
            if (dp[i][j] && len >= L) {
                seen.insert(getHash(i, j));
            }
        }
    }
    return seen.size();
}

11. 进一步优化

如果要处理更大 n 或更严格去重，可用回文自动机（Palindromic Tree），它能在 O(n) 时间统计所有不同回文子串，并轻松支持长度限制过滤。不过它的原理比动态规划复杂，这里先介绍动态规划解法以便理解。

这样，我们就循序渐进地讲解了用动态规划解决“统计不同回文子串个数，且长度至少为 L”的问题，从状态定义、转移方程、去重处理到代码实现，每个步骤都做了细致说明。