Count Different Palindromic Subsequences

hard dp string interval dp

Problem

Given a string s of lowercase letters from {a,b,c,d}, count the number of distinct non-empty palindromic subsequences modulo 1_000_000_007. Two subsequences are different if their character sequences differ.

Inputs="bccb"

Output6

The palindromic subsequences are b, c, bb, cc, bcb and bccb.

input

def countPalindromicSubsequences(s):
    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]:
                lo, hi = i + 1, 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) % MOD
                elif lo == hi: dp[i][j] = (2 * dp[i+1][j-1] + 1) % MOD
                else: dp[i][j] = (2 * dp[i+1][j-1] - dp[lo+1][hi-1]) % MOD
            else:
                dp[i][j] = (dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]) % MOD
    return dp[0][n-1] % MOD

function countPalindromicSubsequences(s) {
  const MOD = 1_000_000_007n, n = s.length;
  const dp = Array.from({length: n}, () => new BigInt64Array(n));
  for (let i = 0; i < n; i++) dp[i][i] = 1n;
  for (let len = 2; len <= n; len++) for (let i = 0; i + len <= n; i++) {
    const j = i + len - 1;
    if (s[i] === s[j]) {
      let lo = i + 1, hi = j - 1;
      while (lo <= hi && s[lo] !== s[i]) lo++;
      while (lo <= hi && s[hi] !== s[i]) hi--;
      if (lo > hi) dp[i][j] = (2n * dp[i+1][j-1] + 2n) % MOD;
      else if (lo === hi) dp[i][j] = (2n * dp[i+1][j-1] + 1n) % MOD;
      else dp[i][j] = (2n * dp[i+1][j-1] - dp[lo+1][hi-1] + MOD) % MOD;
    } else dp[i][j] = (dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] + MOD) % MOD;
  }
  return Number(dp[0][n-1]);
}

class Solution {
  public int countPalindromicSubsequences(String s) {
    int MOD = 1_000_000_007, n = s.length();
    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 <= n; i++) {
      int j = i + len - 1;
      if (s.charAt(i) == s.charAt(j)) {
        int lo = i + 1, hi = j - 1;
        while (lo <= hi && s.charAt(lo) != s.charAt(i)) lo++;
        while (lo <= hi && s.charAt(hi) != s.charAt(i)) hi--;
        if (lo > hi) dp[i][j] = (2 * dp[i+1][j-1] + 2) % MOD;
        else if (lo == hi) dp[i][j] = (2 * dp[i+1][j-1] + 1) % MOD;
        else dp[i][j] = (2 * dp[i+1][j-1] - dp[lo+1][hi-1] + MOD) % MOD;
      } else dp[i][j] = (dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] + MOD) % MOD;
    }
    return (int)((dp[0][n-1] + MOD) % MOD);
  }
}

class Solution {
public:
  int countPalindromicSubsequences(string s) {
    const int MOD = 1e9 + 7; int n = s.size();
    vector<vector<long>> dp(n, vector<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 <= n; i++) {
      int j = i + len - 1;
      if (s[i] == s[j]) {
        int lo = i + 1, hi = j - 1;
        while (lo <= hi && s[lo] != s[i]) lo++;
        while (lo <= hi && s[hi] != s[i]) hi--;
        if (lo > hi) dp[i][j] = (2 * dp[i+1][j-1] + 2) % MOD;
        else if (lo == hi) dp[i][j] = (2 * dp[i+1][j-1] + 1) % MOD;
        else dp[i][j] = (2 * dp[i+1][j-1] - dp[lo+1][hi-1] + MOD) % MOD;
      } else dp[i][j] = (dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] + MOD) % MOD;
    }
    return (int)((dp[0][n-1] + MOD) % MOD);
  }
};

Explanation

We count distinct palindromic subsequences inside every substring, building from short ranges to long ones. This is an interval DP where dp[i][j] = the number of distinct palindromes in s[i..j]. The tricky part is avoiding double-counting, which we handle by looking at the two end characters.

The base case is single characters: dp[i][i] = 1, since one letter is itself a palindrome.

When the endpoints differ (s[i] != s[j]) we use inclusion-exclusion: dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]. The first two terms cover palindromes that drop one end; we subtract the middle overlap counted twice.

When the endpoints match, every inner palindrome can be wrapped by this character, contributing 2 * dp[i+1][j-1]. We then scan inward for another copy of that same character: if there's none we add 2 (for the single letter and the pair), if exactly one we add 1, and if two or more we subtract the inner duplicates dp[lo+1][hi-1] to avoid recounting.

Everything is taken modulo 1_000_000_007. Example: s = "bccb" yields 6 distinct palindromes: b, c, bb, cc, bcb, bccb, which lands in dp[0][n-1].

Time: O(n^2) Space: O(n^2)