LeetCode Solutions Blog

Count Palindromic Subsequences

Number: 2577

Difficulty: Hard

Paid? No

Problem Description

Given a string of digits s, count the number of palindromic subsequences of s having length 5. A palindromic string reads the same forward and backward. Since the answer may be very large, return it modulo 10^9 + 7. Note that a subsequence is obtained by deleting some or no characters from the string without changing the order of the remaining characters.

Key Insights

A palindromic subsequence of length 5 has the structure a, b, c, b, a.
The outer digits (first and last) must be the same and the inner pair (second and fourth) must be the same.
We can fix a center position (for digit c) and count valid pairs both to the left (for a and b) and to the right (for b and a).
Precomputing count matrices (or “pair frequency” arrays) for the left and right parts allows efficient counting of how many (a, b) pairs exist on each side.
The overall count is (for each center) the sum over all digit pairs of leftPairs[a][b] * rightPairs[b][a].

Space and Time Complexity

Time Complexity: O(n * 100) in the worst case. The constant factor comes from iterating over the 10 possible digits for a and b. Space Complexity: O(1) additional space (apart from input), as the two 10x10 matrices use constant space.

Solution

The idea is to iterate over potential center positions of the palindromic subsequence. For each center index, maintain:

A left pair matrix (leftPairs) to count ordered pairs (a, b) for positions before the center.
A right pair matrix (rightPairs) to count ordered pairs (b, a) for positions after the center. Initially, precompute rightPairs for indices starting from index 1 (since center must have at least two characters on the left); then move the center (from index 2 to n - 3) updating leftPairs and decreasing counts in rightPairs accordingly. For every center index, accumulate for every combination of digits the product leftPairs[a][b] * rightPairs[b][a] (each product gives number of subsequences formed using that center with left side pattern a, b and right side pattern b, a). Be sure to use modulo arithmetic.

Algorithm steps:

Convert character digits to ints.
Precompute a 10x10 matrix for rightPairs for indices from center+1 onward.
Iterate the center over valid positions and update leftPairs and rightPairs dynamically.
Sum up the contributions from each valid center.
Return the result modulo 10^9 + 7.

Code Solutions

# Python solution for Count Palindromic Subsequences

MOD = 10**9 + 7

def count_palindromic_subsequences(s):
    n = len(s)
    digits = [int(ch) for ch in s]

    # Initialize 10x10 matrices for pair counts (for both left and right)
    leftPairs = [[0] * 10 for _ in range(10)]
    rightPairs = [[0] * 10 for _ in range(10)]
    
    # Precompute rightPairs for indices from 2 to n-1 
    # (we need at least a center and two positions on the left, so initially we consider the right region starting at index 2)
    for i in range(2, n):
        for j in range(i+1, n):
            # For a candidate right pair, the order is (digit at i, digit at j)
            d1 = digits[i]
            d2 = digits[j]
            rightPairs[d1][d2] += 1

    result = 0
    # leftSeen will help updating leftPairs. We iterate center at index c from 2 to n-3 
    # so that there remain at least two elements on the right to form a pair.
    # Also, maintain an array "seen" for left side digits.
    leftCount = [0] * 10  # single digit frequency for left side
    
    # Iterate center position from index 2 to n-3 (inclusive)
    for center in range(2, n - 2):
        # When moving to center, update left side with the element just before center (at center - 1)
        new_digit = digits[center - 1]
        # For every previously seen digit, form new left pairs by appending new_digit
        for d in range(10):
            leftPairs[d][new_digit] += leftCount[d]
        leftCount[new_digit] += 1

        # Remove pairs starting at center in rightPairs. For each pair where the first element is at index center
        # we need to update the rightPairs because the current center now moves figure out of the right segment.
        if center + 1 < n:
            # For every index j > center
            d = digits[center]
            # For pairs starting at 'center', update for every j with center < j < n.
            # Instead of iterating over possible j, we can subtract the contribution of pairs starting exactly at the current center.
            for j in range(center + 1, n):
                d2 = digits[j]
                rightPairs[d][d2] -= 1

        # Now, for the current center, count valid combinations
        for a in range(10):
            for b in range(10):
                # left has (a, b) and right needs (b, a)
                result = (result + leftPairs[a][b] * rightPairs[b][a]) % MOD

    return result

# Example usage:
print(count_palindromic_subsequences("103301"))  # Output: 2
print(count_palindromic_subsequences("0000000")) # Output: 21
print(count_palindromic_subsequences("9999900000")) # Output: 2