题目描述

给定一个字符串 S，找出 S 中不同的非空回文子序列个数，并 返回该数字与 10^9 + 7 的模。

通过从 S 中删除 0 个或多个字符来获得子字符序列。

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

如果对于某个 i，A_i != B_i，那么 A_1, A_2, ... 和 B_1, B_2, ... 这两个字符序列是不同的。

样例

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

输入：
S = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
输出：104860361
解释：
共有 3104860382 个不同的非空回文子序列，对 10^9 + 7 取模为 104860361。

限制

• S 的长度在 [1, 1000] 范围内。
• S[i] 的每个字符属于集合 {'a', 'b', 'c', 'd'}。

算法

(动态规划) $O(n^2)$

1. 定义 $f(i, j)$ 表示闭区间 [i, j] 包括空串的方案数。
2. 初始时，$f(i, j) = 1$，所有区间都含有默认的空串。
3. 转移时，对于区间 [i, j]
   • 如果某个字符存在，则累加单独这个字符的一种情况。
   • 如果某个字符存在多次，则找到区间内最靠左的位置 $l$ 和最靠右的位置 $r$
     • 如果 $l + 1 = r$，则表示这是一对相邻的字符，这个字符只能贡献一种情况。
     • 其余情况，转移 $f(i, j) = f(i, j) + f(l + 1, r - 1)$。
4. 每个字符的位置信息可以动态维护，即 $i$ 从 $n - 1$ 到 $0$ 枚举，$j$ 从 $i$ 到 $n - 1$ 枚举。
5. 最终需要将整个区间中为空串的情况去除掉。

时间复杂度

• 状态数为 $O(n^2)$，每次转移仅需要枚举 $4$ 个字符，故时间复杂度为 $O(n^2)$。

空间复杂度

• 需要的状态数为 $O(n^2)$，故空间复杂度为 $O(n^2)$。

C++ 代码

const int N = 1000;

class Solution {
private:
    int f[N][N];

public:
    int countPalindromicSubsequences(string S) {
        const int mod = 1000000007;
        const int n = S.length();

        int l[4];
        memset(l, -1, sizeof(l));

        for (int i = n - 1; i >= 0; i--) {
            l[S[i] - 'a'] = i;

            int r[4];
            memset(r, -1, sizeof(r));
            for (int j = i; j < n; j++) {
                r[S[j] - 'a'] = j;
                f[i][j] = 1; // 空串

                for (int c = 0; c < 4; c++) {
                    if (l[c] == -1 || r[c] == -1)
                        continue;

                    f[i][j] = (f[i][j] + 1) % mod; // 单个字符
                    if (l[c] == r[c])
                        continue;


                    if (l[c] + 1 == r[c]) // 位置相邻，有一种情况
                        f[i][j] = (f[i][j] + 1) % mod;
                    else // 其余情况，正常转移
                        f[i][j] = (f[i][j] + f[l[c] + 1][r[c] - 1]) % mod;
                }
            }
        }

        return (f[0][n - 1] + mod - 1) % mod;
    }
};