题目描述

给定一个字符串 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 的长度将在[1, 1000]范围内。
• 每个字符 S[i] 将会是集合 {‘a’, ‘b’, ‘c’, ‘d’} 中的某一个。

算法1

(区间DP + 双端队列) $O(n^2)$

• 状态表示：f[i][j]表示s[i]到s[j]中包含的不同回文子序列个数，包含空串，答案为f[0][n-1] - 1
• 状态转移：对于某个区间[i, j]，找到区间内最左边的和最右边的相同字符，下标为l和r，f[i][j] += f[l + 1][r - 1]
• 由于区间DP枚举左右端点的性质，可以用一个双端队列维护这个过程：右端点更新时入队，左端点更新时出队。
• 对于每个不同字母都开一个deque，如果区间内包含某个字母，则区间内不同子序列个数加一，再判断是否有两个及以上不同的字符，进行状态转移；如果区间内不包含某个字符，则判断下一个字符

Java 代码

class Solution {
    public int countPalindromicSubsequences(String s) {
        int n = s.length();
        int mod = (int)1e9 + 7;
        // f[i][j]表示s[i~j]中回文子序列个数，包含空串
        int[][] f = new int[n][n];
        for(int[] ff: f) Arrays.fill(ff, 1);
        // 单字符，包含空串
        for(int i = 0; i < n; i++) f[i][i] = 2;
        for(int len = 2; len <= n; len++){
            Deque<Integer>[] dq = new Deque[4];
            for(int i = 0; i < 4; i++){
                dq[i] = new LinkedList<>();
            }
            for(int i = 0; i < len - 1; i++){
                dq[s.charAt(i) - 'a'].offerLast(i);
            }
            for(int i = 0; i + len - 1 < n; i++){
                int j = i + len - 1;
                dq[s.charAt(j) - 'a'].offerLast(j);
                for(int k = 0; k < 4; k++){
                    if(dq[k].size() > 0){
                        f[i][j]++;
                        int l = dq[k].peekFirst();
                        int r = dq[k].peekLast();
                        if(l < r){
                            f[i][j] = (f[i][j] + f[l + 1][r - 1]) % mod;
                        }
                    }
                }
                dq[s.charAt(i) - 'a'].pollFirst();
            }
        }
        return f[0][n-1] - 1;
    }
}