HardStringDynamic Programming

Count Different Palindromic Subsequences

1 approach, code in every language

You are given a string `s`. Count the number of distinct non-empty subsequences of `s` that read the same forwards and backwards. Because this total can be enormous, return it modulo `10^9 + 7`.

A subsequence is formed by deleting zero or more characters while preserving order. Two palindromic subsequences are considered the same if the resulting strings are identical, regardless of which positions were selected, so only unique strings should be counted.

Example 1

Input: s = "bccb"

Output: 6

The distinct palindromic subsequences are `b`, `c`, `bb`, `cc`, `bcb`, and `bccb`. The two ways of selecting `bb` count only once.

Example 2

Input: s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"

Output: 104860361

The raw count is astronomically large, so the answer is reduced modulo 10^9 + 7.

Constraints

1 <= s.length <= 1000
s consists of only the characters 'a', 'b', 'c', or 'd'.

Range DP with Inclusion-Exclusion

Solve every substring from short to long, combining smaller ranges and using inclusion-exclusion to cancel duplicates when the ends match.

Loading animation…

Intuition

Let `dp[i][j]` be the number of distinct palindromic subsequences inside the substring `s[i..j]`. When the two endpoints differ, any palindrome lives either in `s[i+1..j]` or `s[i..j-1]`, but palindromes contained in the shared interior `s[i+1..j-1]` are counted twice, so we subtract that overlap. When the endpoints are equal, we can wrap every interior palindrome with the matching character and also add the two single-character and double-character palindromes, but only if no identical character already sits strictly inside; otherwise those wrapped forms would be duplicated. To handle that we locate the leftmost and rightmost occurrences of the endpoint character between `i` and `j`. Careful modular arithmetic (adding the modulus before taking the remainder) keeps every value non-negative after the subtractions.

Algorithm walkthrough

1Initialize `dp[i][i] = 1` because a single character is one palindrome by itself.
2Process substrings in increasing length so every `dp` value on the right-hand side is already known.
3If `s[i] != s[j]`, set `dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]` to merge both sides and remove the doubly counted interior.
4If `s[i] == s[j]`, scan inward for the nearest matching character on each side to determine how many copies of that character lie strictly between `i` and `j`.
5With no interior copy add `2 * dp[i+1][j-1] + 2`, with exactly one add `2 * dp[i+1][j-1] + 1`, and with two or more use `2 * dp[i+1][j-1] - dp[low+1][high-1]` to cancel duplicates.
6After each assignment, normalize with `(value % MOD + MOD) % MOD` and finally return `dp[0][n-1]`.

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:
                    low, high = i + 1, j - 1
                    while low <= high and s[low] != s[i]:
                        low += 1
                    while low <= high and s[high] != s[i]:
                        high -= 1
                    if low > high:
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 2
                    elif 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]
                dp[i][j] = (dp[i][j] + MOD) % MOD
        return dp[0][n - 1]

Time

O(n^2)

Space

O(n^2)

There are O(n^2) substrings, and each is resolved with a constant number of table lookups plus an inward scan that is bounded by the alphabet of four characters. The inner scans are effectively O(1) per state given the tiny alphabet.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free