线性动态规划：最长回文子串的另一种变种——统计不同回文子串的个数（进阶版：统计长度至少为L的不同回文子串个数）

题目描述
给你一个字符串 s，以及一个整数 L。要求统计字符串 s 中不同回文子串的个数，并且只考虑长度至少为 L 的回文子串。

• 子串定义为字符串中连续的字符序列。
• 回文子串是指正着读和反着读都相同的子串。
• 不同回文子串指的是内容不同的子串，即使起始和结束位置不同，只要内容相同就算同一个。
• 长度至少为 L 表示只统计长度大于等于 L 的回文子串。

例如：
输入：s = "ababa", L = 2
输出：3
解释：长度至少为 2 的不同回文子串有 "aba"、"bab"、"ababa"，注意 "aa" 不存在，"a" 和 "b" 长度小于 2 不统计。

解题思路循序渐进讲解

步骤1：问题拆解
我们最终目标是“统计不同回文子串的个数”，且长度至少为 L。
直接思路：

1. 找出所有回文子串。
2. 去重，只保留不同的。
3. 只统计长度 ≥ L 的。

难点在于如何高效枚举并去重。
暴力枚举所有子串是 O(n²) 个，对每个检查回文又是 O(n)，总 O(n³)，再配合哈希集合去重，在 n 较大时不可行。
我们需要一个更高效的方法。

步骤2：动态规划判断回文子串
经典方法：用二维布尔数组 dp[i][j] 表示子串 s[i..j] 是否是回文。
转移方程：

• 如果 s[i] == s[j] 且 (j - i <= 2 或 dp[i+1][j-1] 为真)，则 dp[i][j] = true。
• 否则 dp[i][j] = false。
  这样我们可以在 O(n²) 时间得到所有回文子串的信息。

步骤3：去重与统计
在动态规划填充 dp[i][j] 的过程中，当发现一个回文子串 s[i..j] 时，我们将其加入一个哈希集合（例如 unordered_set<string> 或 set<string>）来去重。
但这样每次需要生成子串（s.substr(i, j-i+1)），会引入 O(n) 的子串构造时间，最坏情况下总复杂度仍可能接近 O(n³)。
为了优化，我们可以用哈希值代替子串内容。

步骤4：使用哈希函数去重
常见的优化：

• 对每个子串计算一个哈希值（如双哈希避免碰撞）。
• 当 dp[i][j] 为真且长度 ≥ L 时，将其哈希值存入集合。
• 最后集合的大小就是答案。

双哈希方法：
用两个不同的质数底数和模数，计算子串的正向哈希和反向哈希，如果正向哈希值等于反向哈希值，则可作为回文的快速验证（但这里我们已经用 dp 判断回文，哈希主要用于去重，所以只需一个哈希函数即可去重）。
但注意：不同子串可能有相同哈希值（碰撞），但我们可以用双哈希降低碰撞概率到可接受范围。

这里为了精确去重，我们依然可以存储子串，但用滚动哈希快速生成子串哈希值，并用哈希值代表子串存入集合。
由于 dp 遍历顺序是子串长度递增，我们可以预处理字符串的哈希数组，以便 O(1) 时间得到任意子串哈希值。

步骤5：算法步骤详细展开

1. 预处理字符串的哈希数组（例如用多项式哈希，基数 base=131, 模数 mod=1e9+7）。
   设 hash[i] 为 s[0..i-1] 的哈希值，则子串 s[l..r] 的哈希值为：

\[ val = (hash[r+1] - hash[l] * pow_base[r-l+1]) \% mod \]

其中 pow_base[k] 是 base^k。

2. 初始化 n = s.length()，dp 为 n×n 的 false 数组，哈希集合 Set 用于存不同回文子串的哈希值。

3. 遍历所有子串长度 len 从 1 到 n：

   • 遍历起始位置 i 从 0 到 n-len：
     • j = i+len-1。
     • 如果 s[i] == s[j] 且 (len <= 2 或 dp[i+1][j-1] 为真)：
       • dp[i][j] = true。
       • 如果 len >= L：计算子串 s[i..j] 的哈希值，加入 Set。

4. 最后 Set 的大小就是答案。

步骤6：复杂度分析

• 时间复杂度：O(n²) 用于 dp 遍历，每次计算哈希 O(1)（因为预处理了哈希数组），总 O(n²)。
• 空间复杂度：O(n²) 用于 dp 数组，O(K) 用于哈希集合，K 是不同回文子串个数。

步骤7：边界情况与实例验证
例1：s = "aaa", L = 2
长度 ≥ 2 的不同回文子串有："aa", "aaa"。共 2 个。
dp 过程：

• len=2: "aa"(0,1), "aa"(1,2) 哈希相同，去重后 1 个。
• len=3: "aaa" 哈希另一个。
  集合大小 = 2 ✅

例2：s = "ababa", L = 2
不同回文子串长度 ≥ 2 的有："aba", "bab", "ababa"。
注意 "aba" 出现了两次（位置0-2和2-4）但内容一样，哈希相同，去重后算 1 个。
集合大小 = 3 ✅

步骤8：进一步优化
我们可以省略 dp 数组，用中心扩展法枚举回文子串，同时计算哈希值并存入集合，这样空间降为 O(1)（不算集合）。
步骤：

• 遍历中心点（奇数长度中心 i，偶数长度中心 i,i+1）。
• 从中心向两边扩展，当 s[l]==s[r] 时，当前子串 s[l..r] 是回文，若长度 ≥ L 则计算哈希值加入集合。
• 扩展直到不匹配或超出边界。
  这样时间仍是 O(n²)（每个中心最多扩展 O(n) 次），但实际比 dp 快一些，且省空间。

步骤9：代码结构示意（中心扩展+哈希去重）

def countDistinctPalindromicSubstrings(s, L):
    n = len(s)
    base, mod = 131, 10**9+7
    pow_base = [1]*(n+1)
    hash_val = [0]*(n+1)
    for i in range(n):
        pow_base[i+1] = (pow_base[i]*base) % mod
        hash_val[i+1] = (hash_val[i]*base + ord(s[i])) % mod
    
    def get_hash(l, r):
        # 子串 s[l..r] 的哈希值
        return (hash_val[r+1] - hash_val[l]*pow_base[r-l+1]) % mod
    
    Set = set()
    
    # 中心扩展
    for center in range(n):
        # 奇数长度
        l = r = center
        while l >= 0 and r < n and s[l] == s[r]:
            if r - l + 1 >= L:
                Set.add(get_hash(l, r))
            l -= 1
            r += 1
        # 偶数长度
        l, r = center, center+1
        while l >= 0 and r < n and s[l] == s[r]:
            if r - l + 1 >= L:
                Set.add(get_hash(l, r))
            l -= 1
            r += 1
    
    return len(Set)

总结
本题结合了回文子串枚举、动态规划或中心扩展、滚动哈希去重三个技巧。
关键点：

1. 用中心扩展法找出所有回文子串。
2. 用多项式哈希在 O(1) 时间得到子串的唯一表示（用双哈希更安全）。
3. 用集合去重，只统计长度 ≥ L 的。

这样就能在 O(n²) 时间高效解决。