#2484

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count Palindromic Subsequences

Count the number of palindromic subsequences of length 5 in a given string of digits.

Problem Statement

Given a string of digits s, your task is to return the number of palindromic subsequences of length 5 in the string. Since the answer may be large, return the result modulo 10^9 + 7.

A palindromic subsequence is a subsequence of the string that reads the same backward as forward. The length of the subsequences considered here must be exactly 5. For example, in s = '103301', two subsequences '10301' and '10301' are palindromic.

Examples

Example 1

Input: s = "103301"

Output: 2

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

All 21 subsequences are "00000", which is palindromic.

Example 3

Input: s = "9999900000"

Output: 2

The only two palindromic subsequences are "99999" and "00000".

Constraints

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

Solution Approach

State Transition Dynamic Programming

The key to solving this problem is recognizing the need for state transition dynamic programming. The state can represent subsequences with certain positions being chosen. You need to consider possible characters for each position of the subsequence and transition accordingly.

Modular Arithmetic for Large Numbers

Due to the large possible result, modular arithmetic must be used. Every time a count is updated, take the result modulo 10^9 + 7 to avoid overflow and ensure correctness.

Efficient Subsequence Counting

To count palindromic subsequences efficiently, use dynamic programming to build possible subsequences of length 5 iteratively, ensuring that you track subsequences' start and end positions properly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity of this problem depend on the approach used. The dynamic programming solution may have time complexity around O(n^2) or higher, depending on the state transitions and optimizations, where n is the length of the string.

What Interviewers Usually Probe

Candidate demonstrates strong understanding of dynamic programming and state transitions.
Candidate can handle modular arithmetic in large-number scenarios.
Candidate shows the ability to break down complex problems into manageable subproblems.

Common Pitfalls or Variants

Common pitfalls

Not using modular arithmetic correctly can lead to overflow errors.
Inefficient state transitions can make the solution too slow for large inputs.
Incorrect counting of subsequences that may result in overcounting or missing valid subsequences.

Follow-up variants

Count palindromic subsequences of a different length.
Count palindromic subsequences of varying lengths dynamically.
Solve for strings that contain non-numeric characters or other constraints.

FAQ

What is the main pattern in the 'Count Palindromic Subsequences' problem?

The main pattern is state transition dynamic programming, where you track subsequences as they are formed, ensuring they meet palindromic conditions.

How does modular arithmetic apply to this problem?

Since the result can be very large, every update to the subsequence count is taken modulo 10^9 + 7 to prevent overflow and keep the answer within limits.

What is a palindromic subsequence?

A palindromic subsequence is a sequence of characters that reads the same forward and backward, with characters picked from a string but not necessarily consecutively.

How can I improve my dynamic programming solution for large inputs?

To improve efficiency, focus on optimizing state transitions and using memoization or tabulation to reduce redundant calculations in dynamic programming.

What are the common mistakes in solving the Count Palindromic Subsequences problem?

Common mistakes include failing to properly handle modular arithmetic, miscounting subsequences, or using inefficient algorithms that don't scale well with large inputs.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

class Solution:
    def countPalindromes(self, s: str) -> int:
        mod = 10**9 + 7
        n = len(s)
        pre = [[[0] * 10 for _ in range(10)] for _ in range(n + 2)]
        suf = [[[0] * 10 for _ in range(10)] for _ in range(n + 2)]
        t = list(map(int, s))
        c = [0] * 10
        for i, v in enumerate(t, 1):
            for j in range(10):
                for k in range(10):
                    pre[i][j][k] = pre[i - 1][j][k]
            for j in range(10):
                pre[i][j][v] += c[j]
            c[v] += 1
        c = [0] * 10
        for i in range(n, 0, -1):
            v = t[i - 1]
            for j in range(10):
                for k in range(10):
                    suf[i][j][k] = suf[i + 1][j][k]
            for j in range(10):
                suf[i][j][v] += c[j]
            c[v] += 1
        ans = 0
        for i in range(1, n + 1):
            for j in range(10):
                for k in range(10):
                    ans += pre[i - 1][j][k] * suf[i + 1][j][k]
                    ans %= mod
        return ans

Continue Practicing

#2478 number of beautiful partitions #2472 maximum number of non overlapping palindrome substrings #2522 partition string into substrings with values at most k