Count Different Palindromic Subsequences

Hard
1039.

Count Different Palindromic Subsequences

Count Different Palindromic Subsequences is a hard coding problem on strings and dynamic programming, asked in Amazon, Google and Uber interviews.

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'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var countPalindromicSubsequences = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Different Palindromic Subsequences — Solution

Count Different Palindromic Subsequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Count Different Palindromic Subsequences is a hard coding problem on strings and dynamic programming, asked in Amazon, Google and Uber interviews.

  • Difficulty: Hard
  • Topics: Strings, Dynamic Programming
  • Asked at: Amazon, Google, Uber
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Count Different Palindromic Subsequences

  1. Hint 1

    Counting distinct strings, not distinct index sets — so identical characters must never be double-counted.

  2. Hint 2

    Let dp[i][j] be the answer for s[i..j]. When the ends differ, inclusion–exclusion on the two shorter intervals works.

  3. Hint 3

    When the ends match, the count depends on how many copies of that character lie strictly between them: none, exactly one, or more.

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]

Java

public static int countPalindromicSubsequences(String s) {
    final long MOD = 1000000007L;
    int n = s.length();
    int[][] nxt = new int[n + 1][4];
    int[][] prv = new int[n + 1][4];
    for (int c = 0; c < 4; c++) nxt[n][c] = n;
    for (int i = n - 1; i >= 0; i--) {
        for (int c = 0; c < 4; c++) nxt[i][c] = nxt[i + 1][c];
        nxt[i][s.charAt(i) - 'a'] = i;
    }
    for (int c = 0; c < 4; c++) prv[0][c] = -1;
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 4; c++) prv[i + 1][c] = prv[i][c];
        prv[i + 1][s.charAt(i) - 'a'] = i;
    }
    long[][] dp = new long[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            long inner = i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0;
            long v;
            if (s.charAt(i) != s.charAt(j)) {
                v = dp[i + 1][j] + dp[i][j - 1] - inner;
            } else {
                int c = s.charAt(i) - 'a';
                int low = nxt[i + 1][c], high = prv[j][c];
                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 (int) dp[0][n - 1];
}

C++

int countPalindromicSubsequences(string s) {
    const long long MOD = 1000000007LL;
    int n = (int) s.size();
    vector<vector<int>> nxt(n + 1, vector<int>(4, n));
    vector<vector<int>> prv(n + 1, vector<int>(4, -1));
    for (int i = n - 1; i >= 0; i--) {
        for (int c = 0; c < 4; c++) nxt[i][c] = nxt[i + 1][c];
        nxt[i][s[i] - 'a'] = i;
    }
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 4; c++) prv[i + 1][c] = prv[i][c];
        prv[i + 1][s[i] - 'a'] = i;
    }
    vector<vector<long long>> dp(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            long long inner = i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0;
            long long v;
            if (s[i] != s[j]) {
                v = dp[i + 1][j] + dp[i][j - 1] - inner;
            } else {
                int c = s[i] - 'a';
                int low = nxt[i + 1][c], high = prv[j][c];
                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 (int) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming