LeetCode 730: Count Different Palindromic Subsequences

Problem Restatement

We are given a string s.

We need to count how many different non-empty palindromic subsequences appear in s.

A subsequence is made by deleting zero or more characters without changing the order of the remaining characters.

A palindrome reads the same forward and backward.

The answer can be large, so we return it modulo:

10**9 + 7

The string contains only the characters 'a', 'b', 'c', and 'd', and its length is at most 1000.

Input and Output

Example function shape:

def countPalindromicSubsequences(s: str) -> int:
    ...

Examples

Example 1

s = "bccb"

The different non-empty palindromic subsequences are:

"b"
"c"
"bb"
"cc"
"bcb"
"bccb"

So the answer is:

6

The sequence "bcb" is counted once, even though it can be formed in more than one way.

Example 2

s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"

The answer is:

104860361

The full count is larger, so the result is returned modulo 10^9 + 7.

First Thought: Generate Subsequences

A direct idea is to generate every subsequence, keep only palindromes, and put them in a set.

This is not feasible.

A string of length n has:

2^n - 1

non-empty subsequences.

Since n can be 1000, explicit generation is impossible.

We need dynamic programming.

Key Insight

Let:

dp[i][j]

mean:

the number of different non-empty palindromic subsequences inside s[i:j+1]

We compute answers for shorter intervals first, then use them to compute longer intervals.

The hard part is avoiding duplicate counting.

If s[i] != s[j], we can combine the two smaller intervals:

dp[i + 1][j]
dp[i][j - 1]

But their overlap:

dp[i + 1][j - 1]

was counted twice, so subtract it.

If s[i] == s[j], then the two equal boundary characters can wrap every palindrome inside s[i+1:j].

But we must check whether the same boundary character appears inside the interval. That determines how many wrapped palindromes are new and how many are duplicates.

Algorithm

Initialize:

dp[i][i] = 1

Each single character is one palindrome.

Then process intervals by increasing length.

For an interval [i, j]:

Case 1: s[i] != s[j]

Use inclusion-exclusion:

dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]

Case 2: s[i] == s[j]

Find the first and last occurrence of s[i] inside the middle interval:

s[i + 1 : j]

Call them lo and hi.

There are three subcases.

If there is no same character inside:

dp[i][j] = 2 * dp[i + 1][j - 1] + 2

The +2 accounts for:

s[i]
s[i] + s[j]

For example, if the boundary character is "b", these are "b" and "bb".

If there is exactly one same character inside:

dp[i][j] = 2 * dp[i + 1][j - 1] + 1

The single-character palindrome already exists, so only one additional boundary-based palindrome is new.

If there are at least two same characters inside:

dp[i][j] = 2 * dp[i + 1][j - 1] - dp[lo + 1][hi - 1]

The subtraction removes palindromes that would be counted twice through the inner pair of the same character.

Apply modulo after every update.

Correctness

For each interval [i, j], dp[i][j] counts distinct non-empty palindromic subsequences inside that interval.

The base case is correct because a one-character interval contains exactly one non-empty palindromic subsequence: the character itself.

When s[i] != s[j], every palindromic subsequence inside s[i:j+1] either avoids s[i], avoids s[j], or avoids both. The first group is counted by dp[i + 1][j]. The second group is counted by dp[i][j - 1]. The subsequences that avoid both are counted in both groups, so subtracting dp[i + 1][j - 1] leaves every distinct palindrome counted once.

When s[i] == s[j], every palindrome in the middle interval can either remain as it is or be wrapped by the matching boundary characters. This gives the 2 * dp[i + 1][j - 1] term. The extra palindromes made only from the boundary character depend on whether that same character already appears inside. With no inner copy, both the single character and double character are new. With one inner copy, the single character already exists, but the double character is new. With two or more inner copies, the palindromes already wrapped by the inner matching pair are duplicated, so dp[lo + 1][hi - 1] removes exactly those duplicates.

The DP fills intervals from shorter to longer, so every referenced subproblem has already been computed. Therefore dp[0][n - 1] gives the number of distinct non-empty palindromic subsequences in the whole string.

Complexity

Let n = len(s).

This version is clear and accepted in many explanations. It can be optimized by precomputing next and previous occurrences, but the interval recurrence is the core idea.

Implementation

class Solution:
    def countPalindromicSubsequences(self, s: str) -> int:
        MOD = 10**9 + 7
        n = len(s)

        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            dp[i][i] = 1

        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1

                if s[i] != s[j]:
                    dp[i][j] = (
                        dp[i + 1][j]
                        + dp[i][j - 1]
                        - dp[i + 1][j - 1]
                    )
                else:
                    lo = i + 1
                    hi = j - 1

                    while lo <= hi and s[lo] != s[i]:
                        lo += 1

                    while lo <= hi and s[hi] != s[i]:
                        hi -= 1

                    if lo > hi:
                        dp[i][j] = 2 * dp[i + 1][j - 1] + 2
                    elif lo == hi:
                        dp[i][j] = 2 * dp[i + 1][j - 1] + 1
                    else:
                        dp[i][j] = (
                            2 * dp[i + 1][j - 1]
                            - dp[lo + 1][hi - 1]
                        )

                dp[i][j] %= MOD

        return dp[0][n - 1]

Code Explanation

We create a square DP table:

dp = [[0] * n for _ in range(n)]

The cell dp[i][j] stores the answer for the substring from index i to index j.

Each single character is one palindrome:

for i in range(n):
    dp[i][i] = 1

We process intervals by length:

for length in range(2, n + 1):

This guarantees that smaller intervals are ready before larger intervals use them.

When the two boundary characters are different, we use inclusion-exclusion:

dp[i][j] = (
    dp[i + 1][j]
    + dp[i][j - 1]
    - dp[i + 1][j - 1]
)

When the boundary characters are the same, we look for duplicate copies inside:

lo = i + 1
hi = j - 1

lo moves right until it finds the same character.

hi moves left until it finds the same character.

If no same character exists inside, we add two new palindromes.

If exactly one exists, we add one new palindrome.

If at least two exist, we subtract the duplicated middle section.

Finally:

dp[i][j] %= MOD

This keeps the result in range and also handles temporary negative values after subtraction.

Testing

def run_tests():
    s = Solution()

    assert s.countPalindromicSubsequences("bccb") == 6
    assert s.countPalindromicSubsequences("a") == 1
    assert s.countPalindromicSubsequences("aa") == 2
    assert s.countPalindromicSubsequences("ab") == 2
    assert s.countPalindromicSubsequences("aaa") == 3
    assert s.countPalindromicSubsequences("aba") == 4
    assert s.countPalindromicSubsequences("abcd") == 4

    assert s.countPalindromicSubsequences(
        "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"
    ) == 104860361

    print("all tests passed")

run_tests()