Practice/Meta/Leetcode 2484. Count Palindromic Subsequences

Leetcode 2484. Count Palindromic Subsequences

CodingMust

Problem

Given a string s consisting of digits (0-9), count the total number of distinct 5-character palindromic subsequences that follow the pattern a-b-c-b-a, where the first and last characters are the same digit, and the second and fourth characters are the same digit.

A subsequence is formed by selecting characters from the original string in order (not necessarily consecutive). The palindromic pattern requires:

• Position 1 and position 5 have the same digit
• Position 2 and position 4 have the same digit
• Position 3 can be any digit

Return the count modulo 10^9 + 7.

Requirements

1. Identify all possible 5-character subsequences that form palindromes matching the a-b-c-b-a pattern
2. Count each unique palindromic pattern exactly once (e.g., "12321" and "12321" from different positions count as the same pattern)
3. Return the result modulo 10^9 + 7
4. Handle strings containing only digits 0-9

Constraints

• 1 ≤ length of s ≤ 10^4
• s consists only of digit characters ('0' through '9')
• Time complexity should be efficient enough to handle the maximum input size
• Space complexity should be reasonable (ideally O(n) or better)

Examples

Example 1:

` Input: s = "103301" Output: 2 Explanation: The valid patterns are "10301" and "03330"

• "10301": outer pair is 1-1, inner pair is 0-0, middle is 3
• "03330": outer pair is 0-0, inner pair is 3-3, middle is 3 `

Example 2:

Input: s = "12321" Output: 1 Explanation: Only one pattern exists: "12321" with outer pair 1-1, inner pair 2-2, middle 3

Example 3:

Input: s = "9999900000" Output: 100 Explanation: Multiple combinations exist with outer pairs \{9-9, 0-0\} and inner pairs from all digit combinations with various middle digits.