Count Palindromic Subsequences — Problem & Solution
Count Palindromic Subsequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Count Palindromic Subsequences is a hard coding problem on strings, dynamic programming and counting, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Strings, Dynamic Programming, Counting
- Asked at: Amazon, Google
- 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
Given a string of digits s, return the number of palindromic subsequences of length 5. Since the answer can be very large, return it modulo 10^9 + 7.
A subsequence is obtained by deleting zero or more characters without changing the order of the rest; two subsequences are different when they use different sets of indices, even if they spell the same digits. A palindrome reads the same forwards and backwards.
Example 1
Input: s = "12321"
Output: 1
Explanation: The only choice is the whole string.
Example 2
Input: s = "0000000"
Output: 21
Explanation: Any 5 of the 7 positions work: C(7, 5) = 21.
Example 3
Input: s = "2026202"
Output: 5
Constraints
1 <= s.length <= 10^4s consists of digits
Hints for Count Palindromic Subsequences
Hint 1
A length-5 palindrome has the shape
a b c b a. Fix the position of the middle characterc— it can be anything.Hint 2
Left of the middle you need the number of index pairs
i < jspellinga b; right of it, the number of pairsl < mspellingb a. Multiply and sum over the 100 choices of(a, b).Hint 3
Maintain those pair counts incrementally as the middle sweeps left to right: adding a digit
cto the left side addscount_left[a]new pairs(a, c)for everya; removing a digit from the right side is the mirror image.
How to solve Count Palindromic Subsequences
With only ten digits, a length-5 palindrome a b c b a is determined around its middle by a pair (a, b). Keep, for the prefix before the middle and the suffix after it, the number of index pairs spelling each of the 100 two-digit patterns; each middle then contributes Σ pre[a][b] · suf[b][a].
Approach
- Precompute the suffix structures for the whole string:
sufCnt[x](digit counts) andsufPair[b][a](pairsl < mwiths[l] = b,s[m] = a), filled by scanning from the right: at digitb, addsufCnt[a]tosufPair[b][a]for everya, then incrementsufCnt[b]. - Sweep the middle
kfrom left to right. First remove indexkfrom the suffix: decrementsufCnt[s[k]], then subtractsufCnt[a]fromsufPair[s[k]][a]for everya. - Add
Σ_{a,b} prePair[a][b] · sufPair[b][a]to the answer (reduce modulo10^9 + 7). - Add index
kto the prefix: for everya, addpreCnt[a]toprePair[a][s[k]]; then incrementpreCnt[s[k]].
Why it works
Every length-5 palindromic subsequence has a unique middle index k, an outer-and-inner pair (i, j) before it spelling a b, and a pair (l, m) after it spelling b a — and any such choice yields a palindrome. So the count for middle k is exactly the sum of products over (a, b). The incremental updates keep pre* describing indices < k and suf* describing indices > k at the moment the middle is evaluated.
Complexity
- Time —
O(100 · n) - Space —
O(100)
Pitfalls
- A single product of two pair counts can reach about 2.5 · 10^15: multiply in 64-bit (or reduce the factors first).
- Remove the middle index from the suffix structures before using them, or pairs that start at the middle itself are counted.
- Different index sets count separately even when they spell the same palindrome.
Reference solution
Python
def countPalindromes(s: str) -> int:
MOD = 10**9 + 7
d = [ord(c) - 48 for c in s]
suf_cnt = [0] * 10
suf_pair = [0] * 100
for b in reversed(d):
base = b * 10
for a in range(10):
suf_pair[base + a] += suf_cnt[a]
suf_cnt[b] += 1
pre_cnt = [0] * 10
pre_pair = [0] * 100
ans = 0
for c in d:
suf_cnt[c] -= 1
base = c * 10
for a in range(10):
suf_pair[base + a] -= suf_cnt[a]
cur = 0
for a in range(10):
for b in range(10):
cur += pre_pair[a * 10 + b] * suf_pair[b * 10 + a]
ans = (ans + cur) % MOD
for a in range(10):
pre_pair[a * 10 + c] += pre_cnt[a]
pre_cnt[c] += 1
return ansJava
public static int countPalindromes(String s) {
final long MOD = 1000000007L;
int n = s.length();
long[] sufCnt = new long[10], sufPair = new long[100], preCnt = new long[10], prePair = new long[100];
for (int i = n - 1; i >= 0; i--) {
int b = s.charAt(i) - '0';
for (int a = 0; a < 10; a++) sufPair[b * 10 + a] += sufCnt[a];
sufCnt[b]++;
}
long ans = 0;
for (int k = 0; k < n; k++) {
int c = s.charAt(k) - '0';
sufCnt[c]--;
for (int a = 0; a < 10; a++) sufPair[c * 10 + a] -= sufCnt[a];
long cur = 0;
for (int a = 0; a < 10; a++) {
for (int b = 0; b < 10; b++) cur += prePair[a * 10 + b] * sufPair[b * 10 + a];
}
ans = (ans + cur % MOD) % MOD;
for (int a = 0; a < 10; a++) prePair[a * 10 + c] += preCnt[a];
preCnt[c]++;
}
return (int) ans;
}C++
int countPalindromes(string s) {
const long long MOD = 1000000007LL;
int n = s.size();
long long sufCnt[10] = {0}, sufPair[100] = {0}, preCnt[10] = {0}, prePair[100] = {0};
for (int i = n - 1; i >= 0; i--) {
int b = s[i] - '0';
for (int a = 0; a < 10; a++) sufPair[b * 10 + a] += sufCnt[a];
sufCnt[b]++;
}
long long ans = 0;
for (int k = 0; k < n; k++) {
int c = s[k] - '0';
sufCnt[c]--;
for (int a = 0; a < 10; a++) sufPair[c * 10 + a] -= sufCnt[a];
long long cur = 0;
for (int a = 0; a < 10; a++) {
for (int b = 0; b < 10; b++) cur += prePair[a * 10 + b] * sufPair[b * 10 + a];
}
ans = (ans + cur % MOD) % MOD;
for (int a = 0; a < 10; a++) prePair[a * 10 + c] += preCnt[a];
preCnt[c]++;
}
return (int)ans;
}JavaScript
var countPalindromes = function(s) {
var MOD = 1000000007;
var n = s.length;
var sufCnt = new Array(10).fill(0), sufPair = new Array(100).fill(0);
for (var i = n - 1; i >= 0; i--) {
var b = s.charCodeAt(i) - 48;
for (var a = 0; a < 10; a++) sufPair[b * 10 + a] += sufCnt[a];
sufCnt[b]++;
}
var preCnt = new Array(10).fill(0), prePair = new Array(100).fill(0);
var ans = 0;
for (var k = 0; k < n; k++) {
var c = s.charCodeAt(k) - 48;
sufCnt[c]--;
for (var a2 = 0; a2 < 10; a2++) sufPair[c * 10 + a2] -= sufCnt[a2];
for (var x = 0; x < 10; x++) {
for (var y = 0; y < 10; y++) {
var p = prePair[x * 10 + y], q = sufPair[y * 10 + x];
if (p && q) ans = (ans + (p % MOD) * (q % MOD) % MOD) % MOD;
}
}
for (var a3 = 0; a3 < 10; a3++) prePair[a3 * 10 + c] += preCnt[a3];
preCnt[c]++;
}
return ans;
};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