> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Count Different Palindromic Subsequences

> Tested Python solution for LeetCode 730 with 35 pytest cases. Generate a practice environment with lcpy.

LeetCode 730, [Hard](/catalog/hard). Topics: [String](/catalog/topics/string), [Dynamic Programming](/catalog/topics/dynamic-programming). [View on LeetCode](https://leetcode.com/problems/count-palindromic-subsequences/description/).

Generate this problem as a practice environment: tested reference solution, 35 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 730   # by problem number
lcpy gen -s count_palindromic_subsequences   # by problem name
```

## Problem

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** `10^9 + 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`.

### Examples

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

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

### Constraints

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/count_palindromic_subsequences/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/count_palindromic_subsequences/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from bisect import bisect_left, bisect_right


class Solution:
    # Time: O(n^2 log n)
    # Space: O(n^2)
    def count_palindromic_subsequences(self, s: str) -> int:
        mod = 1_000_000_007
        n = len(s)
        pos: dict[str, list[int]] = {c: [] for c in "abcd"}
        for i, c in enumerate(s):
            pos[c].append(i)
        # dp[i][j]: number of distinct palindromic subsequences in s[i..j]
        dp = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            dp[i][i] = 1
            for j in range(i + 1, n):
                inner = dp[i + 1][j - 1] if i + 1 <= j - 1 else 0
                if s[i] != s[j]:
                    dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - inner) % mod
                    continue
                # s[i] == s[j] == c: every palindrome either has no c at the
                # ends (counted twice) or is wrapped in a new c layer.
                lst = pos[s[i]]
                k = lst[bisect_right(lst, i)]  # first c strictly inside (i, j)
                if k >= j:
                    dp[i][j] = (2 * inner + 2) % mod
                    continue
                h = lst[bisect_left(lst, j) - 1]  # last c strictly inside (i, j)
                if k == h:
                    dp[i][j] = (2 * inner + 1) % mod
                else:
                    mid = dp[k + 1][h - 1] if k + 1 <= h - 1 else 0
                    dp[i][j] = (2 * inner - mid) % mod
        return dp[0][n - 1]
```

## Complexity

| Time | Space |
| - | - |
| O(n^2 log n) | O(n^2) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.