LeetCode 730 - Count Different Palindromic Subsequences

LeetCode Problem 730

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming

Solution

Problem Understanding

This problem asks us to count how many distinct non-empty palindromic subsequences exist in a string.

A subsequence is formed by deleting characters while preserving the relative order of the remaining characters. Unlike substrings, subsequences do not need to be contiguous.

A palindrome reads the same forward and backward.

The important detail is that we are counting different palindromic subsequences, not the total number of occurrences. If the same palindrome can be formed in multiple ways, it should only be counted once.

For example, in "bccb":

• "b" is a palindrome
• "c" is a palindrome
• "bb" is a palindrome
• "cc" is a palindrome
• "bcb" is a palindrome
• "bccb" is a palindrome

Even though "bcb" can be generated from multiple index combinations, it is counted only once.

The input size is up to 1000, which is large enough that brute force generation of all subsequences is impossible. A string of length 1000 has 2^1000 subsequences, which is astronomically large.

Another important constraint is that characters are restricted to 'a', 'b', 'c', and 'd'. This small alphabet size is a major hint that we can optimize using character-based dynamic programming.

The answer can become extremely large, so we must return it modulo:

10^9 + 7

Important edge cases include:

• A string with only one character
• A string where all characters are identical
• Strings with many duplicate palindromes
• Strings where the same palindrome can be formed in many ways
• Large strings that require efficient memoization or tabulation

The biggest challenge is avoiding duplicate counting.

Approaches

Brute Force Approach

The brute force idea is straightforward:

1. Generate every possible subsequence
2. Check whether each subsequence is a palindrome
3. Insert valid palindromes into a set
4. Return the size of the set

This works because a set naturally removes duplicates.

However, the number of subsequences of a string of length n is:

2^n

For n = 1000, this is completely infeasible.

Even if palindrome checking takes linear time, the exponential number of subsequences makes the approach unusable.

Key Insight for the Optimal Solution

The critical observation is that we do not need to explicitly construct subsequences.

Instead, we can use dynamic programming on substrings.

Define:

dp[i][j]

as the number of distinct palindromic subsequences inside substring:

s[i:j+1]

The difficult part is handling duplicates correctly.

Suppose:

s[i] == s[j]

Then every palindrome inside the middle substring can potentially be wrapped by these matching characters.

For example:

middle palindrome = "c"
wrapping with 'b' gives "bcb"

However, duplicates appear when the same character already exists inside the middle range.

To avoid overcounting, we locate:

• the first occurrence of s[i] inside (i+1, j-1)
• the last occurrence of s[i] inside (i+1, j-1)

This creates three distinct cases:

1. No matching character inside
2. Exactly one matching character inside
3. Multiple matching characters inside

Each case requires a different recurrence relation.

This transforms the problem into a manageable O(n^2) dynamic programming solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(2^n)	Generates all subsequences and checks palindromes
Optimal Dynamic Programming	O(n^2)	O(n^2)	Counts distinct palindromes using interval DP

Algorithm Walkthrough

Step 1: Define the DP State

We create a 2D DP table:

dp[i][j]

which represents the number of distinct non-empty palindromic subsequences in:

s[i:j+1]

Step 2: Initialize Single Characters

Every single character is itself a palindrome.

So:

dp[i][i] = 1

for all i.

Step 3: Process Substrings by Length

We process substrings from shorter to longer.

This ensures smaller subproblems are already solved before larger ones depend on them.

Step 4: Handle Different Boundary Characters

If:

s[i] != s[j]

then we combine results from:

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

But subtract:

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

because it gets counted twice.

So:

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

Step 5: Handle Matching Boundary Characters

If:

s[i] == s[j]

then we search for matching characters inside the interval.

Let:

• left be first occurrence of s[i] inside (i+1, j-1)
• right be last occurrence

Now there are three cases.

Case 1: No Matching Characters Inside

If no matching character exists:

left > right

then:

• all middle palindromes can be wrapped
• plus "s[i]" itself
• plus "s[i]s[j]"

Formula:

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

Case 2: Exactly One Matching Character Inside

If:

left == right

then one duplicate palindrome appears.

Formula:

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

Case 3: Multiple Matching Characters Inside

If:

left < right

then many palindromes were already counted inside.

We subtract the duplicated region:

dp[left+1][right-1]

Formula:

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

Step 6: Apply Modulo

Because subtraction may produce negative values, we normalize using:

MOD = 10^9 + 7

Step 7: Return Final Answer

The result for the entire string is:

dp[0][n-1]

Why it works

The DP works because every palindromic subsequence belongs to one of two categories:

1. It excludes at least one boundary character
2. It includes both boundary characters

The recurrence relations partition these possibilities without missing or double-counting valid palindromes. The careful duplicate handling using left and right guarantees each distinct palindrome is counted exactly once.

Python Solution

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:
                    left = i + 1
                    right = j - 1

                    while left <= right and s[left] != s[i]:
                        left += 1

                    while left <= right and s[right] != s[i]:
                        right -= 1

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

                dp[i][j] %= MOD

        return dp[0][n - 1]

The implementation begins by creating a 2D DP table where each entry stores the number of distinct palindromic subsequences for a substring interval.

The diagonal is initialized to 1 because every single character forms a palindrome.

The outer loop processes substrings in increasing length order. This guarantees all smaller subproblems are already computed before being used.

When the boundary characters differ, the implementation applies the standard inclusion-exclusion principle. We combine counts from removing either boundary and subtract the overlap.

When the boundary characters match, the implementation searches inward to locate duplicate matching characters. These searches determine which recurrence formula should be used.

The modulo operation is applied after every computation to keep values bounded and prevent negative intermediate results from causing issues.

Finally, the algorithm returns the DP value covering the entire string.

Go Solution

func countPalindromicSubsequences(s string) int {
    const MOD int = 1000000007

    n := len(s)

    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
        dp[i][i] = 1
    }

    for length := 2; length <= n; length++ {
        for i := 0; i <= n-length; i++ {
            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 {
                left := i + 1
                right := j - 1

                for left <= right && s[left] != s[i] {
                    left++
                }

                for left <= right && s[right] != s[i] {
                    right--
                }

                if left > right {
                    dp[i][j] = 2*dp[i+1][j-1] + 2
                } else if left == right {
                    dp[i][j] = 2*dp[i+1][j-1] + 1
                } else {
                    dp[i][j] = 2*dp[i+1][j-1] - dp[left+1][right-1]
                }
            }

            dp[i][j] %= MOD

            if dp[i][j] < 0 {
                dp[i][j] += MOD
            }
        }
    }

    return dp[0][n-1]
}

The Go implementation follows the same dynamic programming structure as the Python version.

One important Go-specific detail is handling negative modulo results. In Go, % preserves the sign of the dividend, so subtraction may leave negative values. We explicitly add MOD when necessary.

The DP table is implemented using slices of slices. Since n <= 1000, the O(n^2) memory usage is acceptable.

Worked Examples

Example 1

s = "bccb"

Initial DP Table

Single characters:

i	j	Substring	dp[i][j]
0	0	b	1
1	1	c	1
2	2	c	1
3	3	b	1

Length = 2

Substring "bc"

Characters differ.

dp[0][1] =
dp[1][1] + dp[0][0] - dp[1][0]
= 1 + 1 - 0
= 2

Palindromes:

"b", "c"

Substring "cc"

Characters match.

No matching c inside.

dp[1][2] =
2 * dp[2][1] + 2
= 0 + 2
= 2

Palindromes:

"c", "cc"

Substring "cb"

Characters differ.

dp[2][3] = 2

Length = 3

Substring "bcc"

Characters differ.

dp[0][2] =
dp[1][2] + dp[0][1] - dp[1][1]
= 2 + 2 - 1
= 3

Palindromes:

"b", "c", "cc"

Substring "ccb"

Similarly:

dp[1][3] = 3

Length = 4

Substring "bccb"

Characters match.

Search inside "cc" for 'b'.

No matching 'b' found.

dp[0][3] =
2 * dp[1][2] + 2
= 2 * 2 + 2
= 6

Final palindromes:

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

Answer:

6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	There are O(n^2) DP states
Space	O(n^2)	The DP table stores all substring results

Although the implementation performs inward scans to find duplicate boundary characters, the alphabet size is only four characters. This keeps the practical runtime efficient and accepted within constraints.

The DP table dominates memory usage.

Test Cases

solution = Solution()

assert solution.countPalindromicSubsequences("a") == 1  # single character
assert solution.countPalindromicSubsequences("aa") == 2  # "a", "aa"
assert solution.countPalindromicSubsequences("ab") == 2  # distinct singles
assert solution.countPalindromicSubsequences("aaa") == 3  # "a", "aa", "aaa"
assert solution.countPalindromicSubsequences("bccb") == 6  # provided example
assert solution.countPalindromicSubsequences("abcd") == 4  # no longer palindromes
assert solution.countPalindromicSubsequences("aaaa") == 4  # nested duplicates
assert solution.countPalindromicSubsequences("aba") == 4  # "a", "b", "aa", "aba"
assert solution.countPalindromicSubsequences("abba") == 6  # overlapping structures
assert solution.countPalindromicSubsequences("abcdabcd") > 0  # larger mixed case

Test	Why
"a"	Minimum input size
"aa"	Simple repeated character case
"ab"	No multi-character palindrome
"aaa"	Heavy duplicate generation
"bccb"	Official example
"abcd"	All unique characters
"aaaa"	Duplicate handling stress case
"aba"	Nested palindrome structure
"abba"	Multiple overlapping palindromes
"abcdabcd"	Larger mixed-pattern input

Edge Cases

Single Character Strings

A string like:

"a"

is the smallest valid input.

A common bug is forgetting to initialize base DP states correctly. If dp[i][i] is not initialized to 1, all larger transitions become incorrect.

The implementation explicitly initializes every diagonal cell to 1, guaranteeing single-character palindromes are counted.

Strings With All Identical Characters

Consider:

"aaaa"

Many different subsequence selections generate the same palindrome.

For example:

• "a" can be formed many ways
• "aa" can be formed many ways

A naive counting approach would massively overcount duplicates.

The implementation avoids this by carefully locating duplicate boundary characters and subtracting already-counted regions when necessary.

Overlapping Duplicate Structures

Consider:

"abba"

The palindrome "aba" can arise through different subsequence combinations.

Without proper inclusion-exclusion logic, duplicate counting becomes inevitable.

The recurrence:

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

ensures overlapping regions are counted exactly once.

Negative Values During Subtraction

Some transitions subtract large overlapping ranges.

Without modulo normalization, values may temporarily become negative.

The implementation applies modulo after every update, and the Go version explicitly corrects negative results by adding MOD.