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 <= 1000s[i] is either 'a', 'b', 'c', or 'd'.
Hints for Count Different Palindromic Subsequences
Hint 1
Counting distinct strings, not distinct index sets — so identical characters must never be double-counted.
Hint 2
Let
dp[i][j]be the answer fors[i..j]. When the ends differ, inclusion–exclusion on the two shorter intervals works.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
- Precompute
nxt[i][c](first index ≥iholdingc) andprv[i][c](last index <iholdingc) solowandhighare O(1) lookups. s[i] != s[j]:dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1].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 stringscandcc.- Exactly one copy inside (
low == high):2·dp[i+1][j-1] + 1—calone is already counted inside. - Two or more inside:
2·dp[i+1][j-1] - dp[low+1][high-1]— subtract what the innermost pair double-counts. - Keep everything modulo 10⁹ + 7, adding
MODbefore 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
MODbefore the final%. - The alphabet is only
a–d, which is what makes thenxt/prvtables 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