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.

Description Hints 2 Solution Video 47:22

2484. Count Palindromic Subsequences

Hard41.7% acceptance11 companies

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 10⁹ + 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 <= 10⁴
s consists of digits.

Asked at 11 companies

Visa Citadel Millennium Dialpad Goldman Sachs PhonePe

Google Microsoft Atlassian Uber Amazon

Topics

Dynamic Programming String

Hints open one at a time

Hint 1

There are 100 possibilities for the first two characters of the palindrome.

Hint 2

Iterate over all characters, letting the current character be the center of the palindrome.

47:22

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution