> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dynamic-programming/730.-count-different-palindromic-subsequences.md).

# 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:**<br>

```
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:**<br>

```
Input: 
S = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
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'}`.

```cpp
// Top-Down Dynamic Programming with Memoization
int helper(const string& S, const 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; // new_start exists => single char can be counted, e.g. "a"
        if (new_start != new_end) ++res; // double char can be counted, e.g. "aa"
        res += helper(S, chars, *new_start + 1, *new_end, memo);
    }
    return memo[start][end] = res % (int)(1e9 + 7);
}
int countPalindromicSubsequences(string S) {
    int n = S.length();
    vector<vector<int> > chars(26, vector<int>()), memo(n + 1, vector<int>(n + 1, 0));
    for (int i = 0; i < n; ++i) {
        chars[S[i] - 'a'].emplace_back(i);
    }
    return helper(S, chars, 0, n, memo);
}
```

```cpp
// Bottom-Up Dynamic Programming
int countPalindromicSubsequences(string S) { // time: O(n^3); space: O(n^2)
    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 low = i + 1, high = j - 1;
                while (low <= high && S[low] != S[i]) ++low;
                while (low <= high && S[high] != S[j]) --high;
                if (low > high) dp[i][j] = dp[i + 1][j - 1] * 2 + 2; // a...a, e.g. aba
                else if (low == high) dp[i][j] = dp[i + 1][j - 1] * 2 + 1; // a...a...a, e.g. aaa
                else dp[i][j] = dp[i + 1][j - 1] * 2 - dp[low + 1][high - 1]; // a...a...a...a, e.g. aacaa
            } 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];
}
```