> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0730-count-different-palindromic-subsequences.md).

# 0730. Count Different Palindromic Subsequences

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

## Description

Given a string s, return *the number of different non-empty palindromic subsequences in* `s`. Since the answer may be very large, return it **modulo** `109 + 7`.

A subsequence of a string is obtained by deleting zero or more characters from the string.

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

Two sequences `a1, a2, ...` and `b1, b2, ...` are different if there is some `i` for which `ai != bi`.

**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:** s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"
**Output:** 104860361
**Explanation:** There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 109 + 7.
```

**Constraints:**

* `1 <= s.length <= 1000`
* `s[i]` is either `'a'`, `'b'`, `'c'`, or `'d'`.

## ac

```java
class Solution {
    public int countPalindromicSubsequences(String S) {
        // edge cases
        if (S == null || S.length() == 0) return 0;

        int n = S.length();
        // long[][] dp = new long[n][n];
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                if (S.charAt(j) == S.charAt(i)) {
                    if (j == i || j + 1 == i) {
                        dp[j][i] = i - j + 1;
                    } else {
                        // dedup
                        int l = j + 1, r = i - 1;
                        while (l <= r && S.charAt(l) != S.charAt(j)) l++;
                        while (r >= l && S.charAt(r) != S.charAt(i)) r--;

                        if (l > r) {  // no duplicate, bcb
                            dp[j][i] = 2 * dp[j+1][i-1] + 2;
                        } else if (l == r) {  // 1 duplicate, bcbcb
                            dp[j][i] = 2 * dp[j+1][i-1] + 1;
                        } else { // 2 duplicates, bcbbcb
                            dp[j][i] = 2 * dp[j+1][i-1] - dp[l+1][r-1];
                        }
                    }
                } else {
                    dp[j][i] = dp[j+1][i] + dp[j][i-1] - dp[j+1][i-1];
                }

                dp[j][i] = dp[j][i] < 0 ? dp[j][i] + 1000000007 : dp[j][i] % 1000000007; //why??
            }
        }

        return dp[0][n-1];
        // return (int) (dp[0][n-1] % 1000000007);
    }
}

/*
the key is dedup, and the way is so brilliant, never seen before
*/
```