Watch 10 video solutions for Count Palindromic Subsequences, a hard level problem involving String, Dynamic Programming. This walkthrough by Pepcoding has 62,281 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |