最长回文子序列的变种：统计不同非空回文子序列的个数（进阶版：考虑字符集限制）

题目描述

给定一个字符串s，统计其中所有不同非空回文子序列的个数。注意：这里的"不同"指的是子序列的内容不同，而不是位置不同。同时，题目可能对字符集有限制，比如只包含小写字母'a'到'z'。

例如：

• 输入："bccb"
• 输出：6
• 解释：不同的回文子序列有："b", "c", "bb", "cc", "bcb", "bccb"

解题思路

这个问题是经典的回文子序列计数问题的扩展。我们需要统计所有不同的回文子序列，而不仅仅是计算最长回文子序列的长度。

解题步骤

步骤1：理解问题本质

我们需要找到所有满足以下条件的子序列：

1. 是原字符串的子序列
2. 是回文（正读反读都一样）
3. 内容各不相同

关键难点在于避免重复计数相同的回文序列。

步骤2：定义动态规划状态

我们定义dp[i][j]表示在子串s[i...j]中，所有不同回文子序列的集合。但直接存储集合效率太低，我们可以用更高效的方式。

更好的方法是定义：

• dp[i][j]表示子串s[i...j]中不同回文子序列的个数

但这样还不够，因为我们需要处理重复的情况。我们需要更精细的状态定义。

步骤3：更精细的状态设计

我们定义两个DP数组：

• dp[i][j]：子串s[i...j]中不同回文子序列的个数
• next[i][c]：在位置i右侧，第一个出现字符c的位置
• prev[j][c]：在位置j左侧，第一个出现字符c的位置

这样设计可以帮助我们避免重复计数。

步骤4：状态转移方程

对于区间[i, j]：

1. 如果s[i] == s[j]：
   • 我们考虑所有以s[i]和s[j]作为外层字符的回文序列
   • 为了避免重复，我们需要找到下一个不同的字符位置

具体的状态转移：

# 初始化
for i in range(n):
    dp[i][i] = 1  # 单个字符
    if i < n-1:
        dp[i][i+1] = 2 if s[i] == s[i+1] else 2  # "aa"有2个："a","aa"; "ab"有2个："a","b"

for length from 3 to n:
    for i from 0 to n-length:
        j = i + length - 1
        if s[i] == s[j]:
            # 找到下一个不同的字符位置
            left = i + 1
            right = j - 1
            
            # 跳过重复字符，找到第一个不等于s[i]的字符
            while left <= right and s[left] == s[i]:
                left += 1
            while left <= right and s[right] == s[i]:
                right -= 1
                
            if left > right:
                # 中间所有字符都等于s[i]
                dp[i][j] = dp[i+1][j-1] * 2 + 1
            elif left == right and s[left] == s[i]:
                # 中间只有一个字符且等于s[i]
                dp[i][j] = dp[i+1][j-1] * 2 + 1
            else:
                # 一般情况
                dp[i][j] = dp[i+1][j-1] * 2 - dp[left][right]
        else:
            dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]

步骤5：处理边界情况

• 空序列：题目要求非空，所以不考虑空序列
• 单个字符：每个单个字符都是一个回文子序列
• 两个相同字符："aa"有2个回文子序列："a"和"aa"
• 两个不同字符："ab"有2个回文子序列："a"和"b"

步骤6：完整算法实现

def countPalindromicSubsequences(s: str) -> int:
    n = len(s)
    MOD = 10**9 + 7
    
    # dp[i][j]表示s[i...j]中不同回文子序列的个数
    dp = [[0] * n for _ in range(n)]
    
    # 初始化单个字符
    for i in range(n):
        dp[i][i] = 1
    
    # 填充DP表，按区间长度递增
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            if s[i] == s[j]:
                left = i + 1
                right = j - 1
                
                # 找到第一个不等于s[i]的字符
                while left <= right and s[left] != s[i]:
                    left += 1
                while left <= right and s[right] != s[i]:
                    right -= 1
                
                if left > right:
                    # 情况1：中间没有与两端相同的字符
                    dp[i][j] = dp[i+1][j-1] * 2 + 2
                elif left == right:
                    # 情况2：中间恰好有一个与两端相同的字符
                    dp[i][j] = dp[i+1][j-1] * 2 + 1
                else:
                    # 情况3：中间有多个与两端相同的字符
                    dp[i][j] = dp[i+1][j-1] * 2 - dp[left+1][right-1]
            else:
                # 两端字符不同
                dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
            
            # 处理负数情况
            dp[i][j] %= MOD
            if dp[i][j] < 0:
                dp[i][j] += MOD
    
    return dp[0][n-1]

步骤7：算法正确性验证

以"bccb"为例：

• "b" → 1个："b"
• "c" → 1个："c"
• "cc" → 2个："c", "cc"
• "bc" → 2个："b", "c"
• "cb" → 2个："c", "b"
• "bcc" → 4个："b", "c", "cc", "bcb"
• "ccb" → 4个："c", "cc", "b", "cbc"
• "bccb" → 6个："b", "c", "bb", "cc", "bcb", "bccb"

步骤8：复杂度分析

• 时间复杂度：O(n²)，需要填充n×n的DP表
• 空间复杂度：O(n²)，用于存储DP表

这个算法通过精细的状态设计和去重处理，能够准确统计所有不同的回文子序列，避免了重复计数的问题。