Count Palindromic Subsequences

Count Palindromic Subsequences

What is this problem about?

The "Count Palindromic Subsequences interview question" is a complex counting problem focused on string patterns. You are given a string of digits and you need to find the number of subsequences of length 5 that are palindromes. A length-5 palindrome follows the pattern $a, b, c, b, a$. Since the characters are digits, there are only 100 possible "outer pairs" $(a, b)$.

Why is this asked in interviews?

Companies like Goldman Sachs and Uber ask the "Count Palindromic Subsequences coding problem" to test a candidate's ability to use Dynamic Programming or Prefix/Suffix Pre-calculation. It evaluates whether you can break a length-5 pattern into its symmetrical components and use frequency counts to avoid exponential subsequence generation.

Algorithmic pattern used

This problem follows the Prefix/Suffix Counting and Combinatorial DP patterns.

1. Pattern Breakdown: A length-5 palindrome is $(a, b, ext{any}, b, a)$.
2. Pre-calculation:
   • prefix[i][a][b] stores the number of pairs $(a, b)$ that appear as a subsequence in the string up to index $i$.
   • suffix[i][a][b] stores the number of pairs $(a, b)$ that appear as a subsequence from index $i$ to the end.
3. Global Scan: Iterate through each index $i$ in the string. Treat $s[i]$ as the middle character 'c'.
4. Multiplication: For every possible digit pair $(a, b)$, the number of palindromes with $s[i]$ as the middle is prefix[i-1][a][b] * suffix[i+1][a][b].
5. Modulo: Apply modulo $10^9 + 7$ to all additions.

Example explanation

String: "10301"

• Middle character at index 2 is '3'.
• Prefix pairs before index 2: (1, 0). Count = 1.
• Suffix pairs after index 2: (0, 1). Count = 1.
• Only one palindrome: "10301". Result: 1.

Common mistakes candidates make

• Trying all subsequences: There are $\binom{N}{5}$ subsequences, which is $O(N^5)$, far too slow.
• Incorrect DP state: Failing to recognize that we only need to count pairs of digits, not full palindromes, to build the length-5 result.
• Modulo errors: Forgetting to apply modulo during the multiplication of prefix and suffix counts.

Interview preparation tip

When counting subsequences of a fixed, small length, always look for a way to use "Prefix" and "Suffix" counts. This "Dynamic Programming interview pattern" turns an exponential search into a linear or $O(N imes ext{alphabet}^2)$ pass.