Skip to main content
Talentd

Count Palindromic Subsequences - Solution & Explanation

HardStringDynamic Programming11 min readAsked at: Amazon, Microsoft, Goldman Sachs +8
Practice this problem

Problem Statement

Given a string of digits s, return the number of palindromic subsequences of s having length 5. Since the answer may be very large, return it modulo 109 + 7.

Note:

  • A string is palindromic if it reads the same forward and backward.
  • A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

 

Example 1:

Input: s = "103301"
Output: 2
Explanation: 
There are 6 possible subsequences of length 5: "10330","10331","10301","10301","13301","03301". 
Two of them (both equal to "10301") are palindromic.

Example 2:

Input: s = "0000000"
Output: 21
Explanation: All 21 subsequences are "00000", which is palindromic.

Example 3:

Input: s = "9999900000"
Output: 2
Explanation: The only two palindromic subsequences are "99999" and "00000".

 

Constraints:

  • 1 <= s.length <= 104
  • s consists of digits.

Approach Overview

Problem Overview: Given a string of digits, count how many subsequences form a palindrome of length 5. A valid subsequence follows the pattern a b c b a, where indices increase but characters do not need to be contiguous.

Approach 1: Recursive Approach with Memoization (Exponential → Reduced with DP)

This approach models the problem as a recursive search that builds palindromic subsequences by choosing characters from the left and right ends of the string. The recursion tracks indices and how many characters of the target palindrome pattern remain. Overlapping subproblems appear frequently, so a memoization table stores intermediate results for states like (left, right, remaining_length). This avoids recomputation and converts an exponential search into a manageable dynamic programming solution. Time complexity is roughly O(n²) states with memo lookups, and space complexity is O(n²) for the memo table and recursion stack. This method highlights the subsequence structure clearly and works well when practicing dynamic programming state design.

Approach 2: Dynamic Programming with Combinatorics (O(n * 100))

The optimal solution exploits the fixed palindrome structure a b c b a. Instead of generating subsequences directly, count how many pairs (a,b) appear before a center index and how many matching pairs (b,a) appear after it. Maintain prefix counts of digit pairs and suffix counts of digit pairs for all combinations from 00–99. For each index as the middle character c, multiply the number of prefix pairs (a,b) with suffix pairs (b,a). Summing these products counts all valid palindromes centered at that index. Since digits range from 0–9, there are only 100 pair combinations, making the iteration efficient. Time complexity is O(n * 100), and space complexity is O(n * 100) for prefix/suffix pair counts. This technique combines string processing with dynamic programming style prefix accumulation.

Recommended for interviews: The dynamic programming with combinatorics approach is what interviewers expect. It reduces a seemingly exponential subsequence counting problem into a structured counting task using prefix and suffix frequency tables. Showing the recursive idea first demonstrates understanding of subsequences, but the optimized pair-counting method shows the pattern recognition and optimization skills expected in hard string DP problems.

Approach 1: Dynamic Programming with Combinatorics

We can use a dynamic programming (DP) approach combined with combinatorics to solve this problem efficiently. The idea is that we can calculate the number of palindromic subsequences of length 5 using a DP table where dp[i][j][len] represents the number of palindromic subsequences of length len in the substring s[i...j].

We will use a bottom-up approach to fill this table by considering smaller substrings first and building up to longer ones.

This Python function initializes a 3D DP array to store the number of palindromic subsequences. It uses nested loops where it iteratively builds subsequences of increasing lengths starting from every index. This approach takes advantage of previously computed subsequences to avoid redundant calculations.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n^3) where n is the length of string s.

Space Complexity: O(n^2) due to the DP table storage.

Try this approach in the editor →

Approach 2: Recursive Approach with Memoization

This approach involves using recursion with memoization to count palindromic subsequences. We explore all possible subsequences starting from each possible pair of start and end indices, storing already computed results to avoid redundant calculations.

This approach explores each combination of start and end indices recursively and uses a cache to store results, reducing time complexity substantially over a purely recursive approach.

The Java approach uses recursion with memoization to compute palindromic subsequences. We store intermediate results in a HashMap to avoid redundant calculations. This approach merges recursive depth with memorization strategies to optimize efficiency.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(n^2) through the memoization of pairs of indices.

Space Complexity: O(n^2) due to the memoization storage.

Try this approach in the editor →

Approach 3: Enumeration + Counting

The time complexity is O(100 times n), and the space complexity is O(100 times n). Where n is the length of the string s.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with Combinatorics

Time Complexity: O(n^3) where n is the length of string s.

Space Complexity: O(n^2) due to the DP table storage.

Recursive Approach with Memoization

Time Complexity: O(n^2) through the memoization of pairs of indices.

Space Complexity: O(n^2) due to the memoization storage.

Enumeration + Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive with MemoizationO(n²)O(n²)Useful for understanding subsequence DP state transitions and practicing memoization
Dynamic Programming with CombinatoricsO(n * 100)O(n * 100)Optimal solution when counting fixed-length palindromic subsequences in digit strings

Video Solution

Count Palindromic Subsequences Dynamic Programming | Leetcode Hard Solutions • Pepcoding • 63,119 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Palindromic Subsequences easy or hard?
Count Palindromic Subsequences is classified as a Hard problem on LeetCode. The challenge comes from recognizing the fixed palindrome pattern and transforming subsequence enumeration into a pair-counting dynamic programming problem.
How to solve Count Palindromic Subsequences in O(n)?
Use prefix and suffix pair frequency tables. Track how many pairs (a,b) appear before an index and how many pairs (b,a) appear after it. Treat each position as the center of a length‑5 palindrome and multiply the counts of matching prefix and suffix pairs. Since the digit alphabet size is constant (10), the algorithm effectively runs in linear time relative to the string length.
What is the best approach for Count Palindromic Subsequences?
The most efficient solution uses dynamic programming with combinatorics. It counts digit pairs before and after each index to form palindromes of the form a b c b a. By storing prefix and suffix pair frequencies for all digit pairs (00–99), the algorithm computes the answer in O(n * 100) time and O(n * 100) space.
Is Count Palindromic Subsequences asked at Google/Amazon/Meta?
Hard string and dynamic programming problems like this frequently appear in interviews at large tech companies such as Google, Amazon, and Meta. The problem tests pattern recognition, prefix counting techniques, and optimization of subsequence enumeration.
What data structure is used in Count Palindromic Subsequences?
The optimal solution uses arrays or matrices to store prefix and suffix digit pair counts. These structures track how often each pair of digits occurs before and after a given index, enabling constant-time lookups when forming palindromic patterns.
What is the time complexity of Count Palindromic Subsequences?
The optimal algorithm runs in O(n * 100) time because there are only 100 possible digit pairs (00–99) and each index is processed once. Space complexity is also O(n * 100) to maintain prefix and suffix pair counts used for combining valid palindromic patterns.
Count Palindromic Subsequences Python or Java solution approach?
Python and Java implementations typically build prefix pair counts and suffix pair counts using 2D arrays of size 10x10. For each index treated as the center character, the algorithm multiplies matching pair frequencies and accumulates the result modulo 1e9+7.

Ready to solve this problem?

Practice Count Palindromic Subsequences with our built-in code editor and test cases.

Practice on FleetCode
Previous

Arithmetic Slices II - Subsequence

Next

Count Different Palindromic Subsequences