Count Palindromic Subsequences

Hard
1261.

Count Palindromic Subsequences

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

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^4
  • s consists of digits
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 countPalindromes = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^4
  • s consists of digits

Hints for Count Palindromic Subsequences

  1. Hint 1

    A length-5 palindrome has the shape a b c b a. Fix the position of the middle character c — it can be anything.

  2. Hint 2

    Left of the middle you need the number of index pairs i < j spelling a b; right of it, the number of pairs l < m spelling b a. Multiply and sum over the 100 choices of (a, b).

  3. Hint 3

    Maintain those pair counts incrementally as the middle sweeps left to right: adding a digit c to the left side adds count_left[a] new pairs (a, c) for every a; 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

  1. Precompute the suffix structures for the whole string: sufCnt[x] (digit counts) and sufPair[b][a] (pairs l < m with s[l] = b, s[m] = a), filled by scanning from the right: at digit b, add sufCnt[a] to sufPair[b][a] for every a, then increment sufCnt[b].
  2. Sweep the middle k from left to right. First remove index k from the suffix: decrement sufCnt[s[k]], then subtract sufCnt[a] from sufPair[s[k]][a] for every a.
  3. Add Σ_{a,b} prePair[a][b] · sufPair[b][a] to the answer (reduce modulo 10^9 + 7).
  4. Add index k to the prefix: for every a, add preCnt[a] to prePair[a][s[k]]; then increment preCnt[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 ans

Java

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