统计不同回文子序列

难度: Hard

给你一个字符串 s ，返回 s 中不同的非空回文子序列个数。由于答案可能很大，请返回对 10⁹ + 7 取余的结果。

字符串的子序列可以经由字符串删除 0 个或多个字符获得。

如果一个序列与它反转后的序列一致，那么它是回文序列。

如果存在某个 i , 满足 a_i != b_i，则两个序列 a₁, a₂, ... 和 b₁, b₂, ... 不同。

示例 1：

输入：s = 'bccb'
输出：6
解释：6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。
注意：'bcb' 虽然出现两次但仅计数一次。

示例 2：

输入：s = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
输出：104860361
解释：共有 3104860382 个不同的非空回文子序列，104860361 是对 10⁹ + 7 取余后的值。

提示：

1 <= s.length <= 1000
s[i] 仅包含 'a', 'b', 'c' 或 'd'

Submission

运行时间: 296 ms

内存: 16.2 MB

class Solution:
    def countPalindromicSubsequences(self, s: str) -> int:
        n=len(s)
        mod=10**9+7
        nxt=[0]*n
        use=[0]*n
        ans=0
        for j in range(n):
            x=1
            for i in range(j-1,-1,-1):
                if s[i]==s[j]:
                    now_nxt=nxt[i]
                    now_use=use[i]
                    nxt[i]+=x
                    x=now_nxt-now_use+1
                    use[i]=now_nxt+1
                else:nxt[i]+=x
            ans+=x
        return ans%mod

Explain

这个题解使用动态规划的思想解决问题。通过维护两个数组nxt和use，nxt[i]表示以s[i]结尾的回文子序列个数，use[i]表示以s[i]结尾且s[i]已经使用过的回文子序列个数。遍历字符串s，对于每个位置j，从j-1到0遍历所有i，如果s[i]==s[j]，则将nxt[i]加到答案中，并更新nxt[i]和use[i]。如果s[i]!=s[j]，则只更新nxt[i]。最终返回答案对10^9+7取模的结果。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def countPalindromicSubsequences(self, s: str) -> int:
        n = len(s)
        mod = 10**9 + 7
        nxt = [0] * n  # nxt[i]表示以s[i]结尾的回文子序列个数
        use = [0] * n  # use[i]表示以s[i]结尾且s[i]已经使用过的回文子序列个数
        ans = 0
        for j in range(n):
            x = 1
            for i in range(j-1, -1, -1):
                if s[i] == s[j]:
                    now_nxt = nxt[i]
                    now_use = use[i]
                    nxt[i] += x  # 更新nxt[i]
                    x = now_nxt - now_use + 1  # 更新x
                    use[i] = now_nxt + 1  # 更新use[i]
                else:
                    nxt[i] += x  # 更新nxt[i]
            ans += x  # 将x加到答案中
        return ans % mod

Explore

在这个动态规划方案中，数组`nxt`和`use`用于跟踪以每个字符`s[i]`结尾的回文子序列的状态。`nxt[i]`表示以`s[i]`结尾的回文子序列的个数。这包括所有以`s[i]`作为结尾的回文子序列，无论它们的开始位置在哪里。`use[i]`则记录了在字符`s[i]`上结尾且该字符在此之前已经在其他回文子序列中作为结尾使用过的子序列的个数。这样，`use[i]`帮助我们避免计算重复的子序列，确保每个子序列只被计算一次。

当`s[i] == s[j]`时，意味着我们找到了一个新的可能的回文子序列的开始和结束点。此时，`nxt[i]`需要更新，因为我们可以通过将`s[j]`添加到以`s[i]`结尾的所有子序列来形成新的回文子序列。具体来说，`nxt[i]`的更新为`nxt[i] += x`，其中`x`是从上一个匹配的字符到当前字符`s[j]`之间的回文子序列个数。`use[i]`则记录更新前的`nxt[i]`，这样可以在后续的计算中使用，以确保不重复计算已经计算过的子序列。这种更新方式确保了能够正确地统计不同的回文子序列，尤其是涉及到重复字符的情况。

变量`x`在算法中代表新增加的回文子序列的数量，这些子序列是由当前考虑的字符`s[j]`新增至以前的子序列中形成的。在每一轮外层循环（对于每个`s[j]`），`x`初始被设置为1，表示单个字符`s[j]`本身也是一个回文子序列。在内层循环中，每当找到一个与`s[j]`相同的字符`s[i]`时，`x`被更新为与`s[i]`有关的新增回文子序列个数，这是通过计算`nxt[i] - use[i] + 1`得到的，其中`+1`代表添加由`s[i]`和`s[j]`形成的新回文子序列。这样的更新确保了`x`始终代表从上一个匹配点到当前点新增的回文子序列数。