## Algorithm

Problem Name: 730. Count Different Palindromic Subsequences

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'`.

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const countPalindromicSubsequences = function(S) {
const len = S.length
const dp = Array.from({ length: len }, () => new Array(len).fill(0))
const mod = 10 ** 9 + 7
for (let i = 0; i < len; i++) dp[i][i] = 1
for (let distance = 1; distance < len; distance++) {
for (let i = 0; i < len - distance; i++) {
let j = i + distance
if (S[i] === S[j]) {
let low = i + 1
let high = j - 1
while (low <= high && S[low] != S[j]) low++
while (low <= high && S[high] != S[j]) high--
if (low > high) {
dp[i][j] = dp[i + 1][j - 1] * 2 + 2
} else if (low == high) {
dp[i][j] = dp[i + 1][j - 1] * 2 + 1
} else {
dp[i][j] = dp[i + 1][j - 1] * 2 - dp[low + 1][high - 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] + mod : dp[i][j] % mod
}
}
return dp[len - 1]
}
``````
Copy The Code &

Input

cmd
s = "bccb"

Output

cmd
6

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def countPalindromicSubsequences(self, S):
mod, memo = 10 ** 9 + 7, {}
def dfs(i, j):
if (i, j) not in memo:
cnt = 0
for x in "abcd":
try: l, r = S[i:j + 1].index(x) + i, S[i:j + 1].rindex(x) + i
except: continue
cnt += l != r and dfs(l + 1, r - 1) + 2 or 1
memo[(i, j)] = cnt % mod
return memo[(i, j)]
return dfs(0, len(S) - 1)
``````
Copy The Code &

Input

cmd
s = "bccb"

Output

cmd
6