Problem Overview & Intuition

Let dp[i][j] be the number of palindromic subsequences in s[i...j]. By the inclusion-exclusion principle: when s[i] !== s[j], count is dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]. When s[i] === s[j], any palindrome in s[i+1...j-1] can be wrapped by s[i] and s[j], plus the pair {s[i], s[j]} itself.

Step-by-Step Approach

1. Initialize dp[n][n] table with BigInt values modulo 10^9 + 7.
2. Base cases: dp[i][i] = 1.
3. Iterate interval length len from 2 to n.
4. If s[i] === s[j]: dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] + 1) % MOD.
5. Else: dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + MOD) % MOD.
6. Return Number(dp[0][n - 1]).

Optimal Implementation (JavaScript)

function countPalindromicSubsequences(s) {
  const n = s.length;
  const MOD = 1000000007n;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0n));
  for (let i = 0; i < n; i++) dp[i][i] = 1n;
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      if (s[i] === s[j]) {
        dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] + 1n) % 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]);
}

Complexity Analysis