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:
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 <= 104s consists of digits.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.
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.
Time Complexity: O(n^3) where n is the length of string s.
Space Complexity: O(n^2) due to the DP table storage.
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.
Time Complexity: O(n^2) through the memoization of pairs of indices.
Space Complexity: O(n^2) due to the memoization storage.
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.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Combinatorics | Time Complexity: Space Complexity: |
| Recursive Approach with Memoization | Time Complexity: Space Complexity: |
| Enumeration + Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(n²) | O(n²) | Useful for understanding subsequence DP state transitions and practicing memoization |
| Dynamic Programming with Combinatorics | O(n * 100) | O(n * 100) | Optimal solution when counting fixed-length palindromic subsequences in digit strings |
Count Palindromic Subsequences Dynamic Programming | Leetcode Hard Solutions • Pepcoding • 62,281 views views
Watch 9 more video solutions →Practice Count Palindromic Subsequences with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor