区间动态规划例题：统计不同回文子字符串数目问题

题目描述
给定一个字符串s，你需要统计其中不同非空回文子字符串的个数。这里的"不同"指的是不同的字符串内容，即使它们来自s的不同位置，只要内容相同就只算一个。

例如：

• 输入："abc"，输出：3（"a"、"b"、"c"）
• 输入："aaa"，输出：3（"a"、"aa"、"aaa"）
• 输入："aba"，输出：4（"a"、"b"、"ab"、"aba"）

解题思路
我们可以使用区间动态规划结合哈希集合来统计所有不同的回文子串。基本思路是：

1. 定义dp[i][j]表示子串s[i...j]是否为回文串
2. 遍历所有可能的子串，判断其是否为回文串
3. 使用集合来存储不同的回文子串

详细解题步骤

步骤1：定义状态
定义二维布尔数组dp，其中dp[i][j]表示字符串s从索引i到索引j的子串是否为回文串。

步骤2：初始化基础情况

• 单个字符一定是回文串：dp[i][i] = true（对所有i）
• 两个相同字符是回文串：如果s[i] == s[i+1]，则dp[i][i+1] = true

步骤3：状态转移方程
对于长度大于2的子串（j-i ≥ 2）：
dp[i][j] = true 当且仅当：

1. s[i] == s[j]（首尾字符相同）
2. dp[i+1][j-1] == true（内部子串是回文串）

步骤4：遍历顺序
由于计算dp[i][j]需要知道dp[i+1][j-1]，我们需要按子串长度从小到大进行遍历：

1. 先遍历长度为1和2的子串（基础情况）
2. 然后依次遍历长度为3, 4, ..., n的子串

步骤5：统计不同回文子串
使用哈希集合来存储所有找到的回文子串，集合会自动去重。

完整代码实现

def countPalindromicSubstrings(s):
    if not s:
        return 0
    
    n = len(s)
    # 创建DP表
    dp = [[False] * n for _ in range(n)]
    # 用于存储不同的回文子串
    palindromes = set()
    
    # 基础情况：长度为1的子串
    for i in range(n):
        dp[i][i] = True
        palindromes.add(s[i])
    
    # 基础情况：长度为2的子串
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            palindromes.add(s[i:i + 2])
    
    # 遍历更长的子串（长度从3到n）
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1  # 子串结束位置
            
            # 检查首尾字符是否相同，且内部子串是否为回文
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                palindromes.add(s[i:j + 1])
    
    return len(palindromes)

步骤6：算法分析

• 时间复杂度：O(n²)，需要填充n×n的DP表
• 空间复杂度：O(n²)，用于存储DP表，以及O(k)用于存储回文子串（k为不同回文子串的数量）

示例演示
以字符串"aba"为例：

1. 长度为1的子串：

   • "a"（位置0）→ 回文 ✓
   • "b"（位置1）→ 回文 ✓
   • "a"（位置2）→ 回文 ✓

2. 长度为2的子串：

   • "ab"（位置0-1）→ 不是回文
   • "ba"（位置1-2）→ 不是回文

3. 长度为3的子串：

   • "aba"（位置0-2）→ 首尾都是'a'，且内部"b"是回文 → 回文 ✓

最终得到4个不同的回文子串："a"、"b"、"aba"。

这种方法通过动态规划高效地识别所有回文子串，并用集合自动去重，准确计算不同回文子串的数量。