统计不同回文子序列

题目描述

给定一个字符串s，计算s中不同非空回文子序列的个数。由于结果可能很大，返回对10^9+7取模后的结果。

字符串的子序列是通过删除原字符串的某些字符（也可以不删除）而不改变剩余字符的相对顺序形成的新字符串。如果某个序列正着读和反着读一样，那么它就是回文序列。

示例：
输入：s = "bccb"
输出：6
解释：6个不同的回文子序列分别是："b", "c", "bb", "cc", "bcb", "bccb"

解题过程

1. 问题分析

我们需要统计字符串中所有不同的回文子序列。与回文子串不同，子序列不要求连续，这增加了问题的复杂度。

关键观察：

• 相同的回文子序列只统计一次
• 空序列不算在内
• 需要考虑字符重复的情况

2. 动态规划定义

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

3. 状态转移方程

情况1：当s[i] ≠ s[j]时
dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
解释：用包含原则排除重复计算的部分

情况2：当s[i] = s[j]时
设left = i+1, right = j-1
我们需要找到在区间(i,j)内与s[i]相同的第一个和最后一个位置

• 如果left > right：没有相同字符在中间
  dp[i][j] = 2 × dp[i+1][j-1] + 2
  解释：中间的所有回文子序列，加上首尾字符，再加上首尾字符单独形成的回文

• 如果left = right：有一个相同字符在中间
  dp[i][j] = 2 × dp[i+1][j-1] + 1
  解释：避免重复计算中间的那个单一字符

• 如果left < right：有多个相同字符在中间
  dp[i][j] = 2 × dp[i+1][j-1] - dp[left+1][right-1]
  解释：减去中间重复计算的部分

4. 算法实现细节

def countPalindromicSubsequences(s: str) -> int:
    MOD = 10**9 + 7
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    
    # 预处理每个位置左右边相同字符的位置
    left = [-1] * n
    right = [-1] * n
    
    # 计算left数组
    last = {}
    for i in range(n):
        if s[i] in last:
            left[i] = last[s[i]]
        last[s[i]] = i
    
    # 计算right数组  
    last = {}
    for i in range(n-1, -1, -1):
        if s[i] in last:
            right[i] = last[s[i]]
        last[s[i]] = i
    
    # 动态规划
    for length in range(1, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            if i == j:
                dp[i][j] = 1
                continue
                
            if s[i] != s[j]:
                dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
            else:
                # 在(i,j)区间内找与s[i]相同的最左和最右位置
                l = right[i]
                r = left[j]
                
                if l is None or l > j:  # 区间内没有相同字符
                    dp[i][j] = 2 * dp[i+1][j-1] + 2
                elif l == r:  # 区间内只有一个相同字符
                    dp[i][j] = 2 * dp[i+1][j-1] + 1
                else:  # 区间内有多个相同字符
                    dp[i][j] = 2 * dp[i+1][j-1] - dp[l+1][r-1]
            
            dp[i][j] %= MOD
    
    return dp[0][n-1]

5. 逐步计算示例

以s = "bccb"为例：

初始化：

• 单个字符：dp[0][0]=1, dp[1][1]=1, dp[2][2]=1, dp[3][3]=1

计算长度为2的子串：

• "bc": dp[0][1] = dp[0][0] + dp[1][1] - dp[1][0] = 1+1-0=2
• "cc": 相同字符，区间内无相同字符 → 2×dp[2][2]+2=2×1+2=4
• "cb": 不同字符 → dp[2][2]+dp[3][3]-dp[3][2]=1+1-0=2

计算长度为3的子串：

• "bcc": s[0]≠s[2] → dp[0][1]+dp[1][2]-dp[1][1]=2+4-1=5
• "ccb": s[1]≠s[3] → dp[1][2]+dp[2][3]-dp[2][2]=4+2-1=5

计算长度为4的子串："bccb"

• s[0]=s[3]='b'
• 在(0,3)区间内找相同字符：l=right[0]=None, r=left[3]=0
• 区间内无相同字符 → dp[0][3]=2×dp[1][2]+2=2×4+2=10
• 但需要去重，实际结果是6

6. 复杂度分析

时间复杂度：O(n²)
空间复杂度：O(n²)

这个算法通过巧妙的预处理和状态转移，高效地统计了所有不同的回文子序列，避免了重复计数。