Count Different Palindromic Subsequences — Hard Problem & Solution

Problem statement

Return the number of different non-empty palindromic subsequences of s, modulo 10⁹ + 7.

Two subsequences are different if the resulting strings differ — the positions chosen do not matter.

Example 1

Input: s = "bccb"
Output: 6
Explanation: `b`, `c`, `bb`, `cc`, `bcb` and `bccb`.

Example 2

Input: s = "aaa"
Output: 3
Explanation: `a`, `aa` and `aaa` — the three single `a`s are the same string.

Example 3

Input: s = "abcd"
Output: 4
Explanation: Only the four single characters.

Constraints

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

How to solve Count Different Palindromic Subsequences

Interval DP with dp[i][j] = the number of distinct palindromic subsequences of s[i..j]. When s[i] != s[j], combine the two sub-intervals with inclusion–exclusion. When they are equal, the answer depends on the innermost and outermost copies of that character strictly inside — call them low and high.

Approach

1. Precompute nxt[i][c] (first index ≥ i holding c) and prv[i][c] (last index < i holding c) so low and high are O(1) lookups.
2. s[i] != s[j]: dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1].
3. s[i] == s[j], no copy inside (low > high): 2·dp[i+1][j-1] + 2 — the inner answers, each optionally wrapped, plus the two new strings c and cc.
4. Exactly one copy inside (low == high): 2·dp[i+1][j-1] + 1 — c alone is already counted inside.
5. Two or more inside: 2·dp[i+1][j-1] - dp[low+1][high-1] — subtract what the innermost pair double-counts.
6. Keep everything modulo 10⁹ + 7, adding MOD before the final reduction since subtractions can go negative.

Why it works

The three cases exist entirely because the count is over strings. Wrapping every inner palindrome in c…c produces a distinct string, hence the factor of 2 — but the palindromes that already begin and end with c inside the interval would be produced twice, and dp[low+1][high-1] is exactly that overlap. Getting the +2 / +1 / − split wrong is the classic way this problem fails: the constants account for whether c and cc are new strings or were already counted deeper inside.

Complexity

• Time — O(n²)
• Space — O(n²)

Pitfalls

• Modular subtraction can go negative — add MOD before the final %.
• The alphabet is only a–d, which is what makes the nxt/prv tables cheap.
• Distinct strings, not distinct index sets: "aaa" has 3 answers, not 7.

Reference solution

Python

def countPalindromicSubsequences(s: str) -> int:
    MOD = 10**9 + 7
    n = len(s)
    nxt = [[n] * 4 for _ in range(n + 1)]
    prv = [[-1] * 4 for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        for c in range(4):
            nxt[i][c] = nxt[i + 1][c]
        nxt[i][ord(s[i]) - 97] = i
    for i in range(n):
        for c in range(4):
            prv[i + 1][c] = prv[i][c] if i > 0 else -1
        prv[i + 1][ord(s[i]) - 97] = i
    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
            inner = dp[i + 1][j - 1] if i + 1 <= j - 1 else 0
            if s[i] != s[j]:
                v = dp[i + 1][j] + dp[i][j - 1] - inner
            else:
                c = ord(s[i]) - 97
                low, high = nxt[i + 1][c], prv[j][c]
                if low > high:
                    v = 2 * inner + 2
                elif low == high:
                    v = 2 * inner + 1
                else:
                    v = 2 * inner - (dp[low + 1][high - 1] if low + 1 <= high - 1 else 0)
            dp[i][j] = (v % MOD + MOD) % MOD
    return dp[0][n - 1]

JavaScript

var countPalindromicSubsequences = function(s) {
    var MOD = 1000000007;
    var n = s.length, i, c, j;
    var nxt = [], prv = [];
    for (i = 0; i <= n; i++) {
        var rowN = [], rowP = [];
        for (c = 0; c < 4; c++) { rowN.push(n); rowP.push(-1); }
        nxt.push(rowN); prv.push(rowP);
    }
    for (i = n - 1; i >= 0; i--) {
        for (c = 0; c < 4; c++) nxt[i][c] = nxt[i + 1][c];
        nxt[i][s.charCodeAt(i) - 97] = i;
    }
    for (i = 0; i < n; i++) {
        for (c = 0; c < 4; c++) prv[i + 1][c] = i > 0 ? prv[i][c] : -1;
        prv[i + 1][s.charCodeAt(i) - 97] = i;
    }
    var dp = [];
    for (i = 0; i < n; i++) {
        var row = [];
        for (j = 0; j < n; j++) row.push(0);
        dp.push(row);
    }
    for (i = 0; i < n; i++) dp[i][i] = 1;
    for (var len = 2; len <= n; len++) {
        for (i = 0; i + len - 1 < n; i++) {
            j = i + len - 1;
            var inner = i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0;
            var v;
            if (s.charAt(i) !== s.charAt(j)) {
                v = dp[i + 1][j] + dp[i][j - 1] - inner;
            } else {
                var ch = s.charCodeAt(i) - 97;
                var low = nxt[i + 1][ch], high = prv[j][ch];
                if (low > high) v = 2 * inner + 2;
                else if (low === high) v = 2 * inner + 1;
                else v = 2 * inner - (low + 1 <= high - 1 ? dp[low + 1][high - 1] : 0);
            }
            dp[i][j] = ((v % MOD) + MOD) % MOD;
        }
    }
    return dp[0][n - 1];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Number of Ways to Separate Numbers Hard
• Form Largest Integer With Digits That Add up to Target Hard
• Restore the Array Hard
• Strange Printer Hard
• Special Binary String Hard
• Smallest K-Length Subsequence With Occurrences of a Letter Hard