# 730. Count Different Palindromic Subsequences

Given a string S, find the number of different non-empty palindromic subsequences in S, and return that number modulo `10^9 + 7`.

A subsequence of a string S is obtained by deleting 0 or more characters from S.

A sequence is palindromic if it is equal to the sequence reversed.

Two sequences `A_1, A_2, ...` and `B_1, B_2, ...` are different if there is some `i` for which `A_i != B_i`.

Example 1:

``````Input:
S = 'bccb'
Output: 6
Explanation:
The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'.
Note that 'bcb' is counted only once, even though it occurs twice.
``````

Example 2:

``````Input:
Output: 104860361
Explanation:
There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 10^9 + 7.
``````

Note:

• The length of `S` will be in the range `[1, 1000]`.
• Each character `S[i]` will be in the set `{'a', 'b', 'c', 'd'}`.

b -> {0, 3}

c -> {1, 2}

``````class Solution {
public:
int countPalindromicSubsequences(string S) {
int n = S.size();
vector<vector<int>> chars(26, vector<int>());
vector<vector<int>> memo(n + 1, vector<int>(n + 1, 0));
for (int i = 0; i < n; ++i) {
chars[S[i] - 'a'].push_back(i);
}
return helper(S, chars, 0, n, memo);
}
int helper(string S, vector<vector<int>>& chars, int start, int end, vector<vector<int>>& memo) {
if (start >= end) return 0;
if (memo[start][end] > 0) return memo[start][end];
long res = 0;
for (int i = 0; i < 26; ++i) {
if (chars[i].empty()) continue;
auto new_start = lower_bound(chars[i].begin(), chars[i].end(), start);
auto new_end = lower_bound(chars[i].begin(), chars[i].end(), end) - 1;
if (new_start == chars[i].end() || *new_start >= end) continue;
++res;
if (new_start != new_end) ++res;
res += helper(S, chars, *new_start + 1, *new_end, memo);
}
memo[start][end] = res % int(1e9 + 7);
return memo[start][end];
}
};
``````

``````  b c c b
b 1 2 3 6
c 0 1 2 3
c 0 0 1 2
b 0 0 0 1
``````

1. 当 left > righ 时，说明中间没有和 S[i] 相同的字母了，就是 “aba” 这种情况，那么就有 dp[i][j] = dp[i + 1][j - 1] * 2 + 2，其中 dp[i + 1][j - 1] 是中间部分的回文子序列个数，为啥要乘2呢，因为中间的所有子序列可以单独存在，也可以再外面包裹上字母a，所以是成对出现的，要乘2。加2的原因是外层的 “a” 和 “aa” 也要统计上。

2. 当 left = right 时，说明中间只有一个和 S[i] 相同的字母，就是 “aaa” 这种情况，那么有 dp[i][j] = dp[i + 1][j - 1] * 2 + 1，其中乘2的部分跟上面的原因相同，加1的原因是单个字母 “a” 的情况已经在中间部分算过了，外层就只能再加上个 “aa” 了。

3. 当 left < right 时，说明中间至少有两个和 S[i] 相同的字母，就是 “aabaa” 这种情况，那么有 dp[i][j] = dp[i + 1][j - 1] * 2 - dp[left + 1][right - 1]，其中乘2的部分跟上面的原因相同，要减去 left 和 right 中间部分的子序列个数的原因是其被计算了两遍，要将多余的减掉。比如说对于  “aabaa”，当检测到 S[0] == S[4] 时，是要根据中间的 “aba” 的回文序列个数来计算，共有四种，分别是 “a”, “b”, “aa”, “aba”，将其分别在左右两边加上a的话，可以得到 “aaa”, “aba”, “aaaa”, “aabaa”，我们发现 “aba” 出现了两次了，这就是要将 dp[2][2] (left = 1, right = 3) 减去的原因。

``````class Solution {
public:
int countPalindromicSubsequences(string S) {
int n = S.size(), M = 1e9 + 7;
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) dp[i][i] = 1;
for (int len = 1; len < n; ++len) {
for (int i = 0; i < n - len; ++i) {
int j = i + len;
if (S[i] == S[j]) {
int left = i + 1, right = j - 1;
while (left <= right && S[left] != S[i]) ++left;
while (left <= right && S[right] != S[i]) --right;
if (left > right) {
dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
} else if (left == right) {
dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
} else {
dp[i][j] = dp[i + 1][j - 1] * 2 - dp[left + 1][right - 1];
}
} else {
dp[i][j] = dp[i][j - 1] + dp[i + 1][j] - dp[i + 1][j - 1];
}
dp[i][j] = (dp[i][j] < 0) ? dp[i][j] + M : dp[i][j] % M;
}
}
return dp[0][n - 1];
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/730

Longest Palindromic Subsequence

Longest Palindromic Substring

Palindromic Substrings

https://leetcode.com/problems/count-different-palindromic-subsequences/

https://leetcode.com/problems/count-different-palindromic-subsequences/discuss/109509/Accepted-Java-Solution-using-memoization

https://leetcode.com/problems/count-different-palindromic-subsequences/discuss/109507/Java-96ms-DP-Solution-with-Detailed-Explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation