LeetCode 2484 - Count Palindromic Subsequences

The problem asks us to count all palindromic subsequences of length 5 within a given string of digits s. A palindromic subsequence is a sequence that reads the same forward and backward, and a subsequence can be formed by deleting zero or more characters without changing the…

leetcodehardstringdynamic-programming

LeetCode Problem 2484

Difficulty: 🔴 Hard
Topics: String, Dynamic Programming

Solution

Problem Understanding

The problem asks us to count all palindromic subsequences of length 5 within a given string of digits s. A palindromic subsequence is a sequence that reads the same forward and backward, and a subsequence can be formed by deleting zero or more characters without changing the order of the remaining characters. For example, given "103301", one valid palindromic subsequence of length 5 is "10301".

The input s is a string of digits with length up to 10,000. The output is the count of palindromic subsequences modulo 10^9 + 7.

Important constraints and implications:

  • 1 <= s.length <= 10^4 implies that a brute-force enumeration of all subsequences is infeasible because there are combinatorially many (O(n^5) for length-5 subsequences).
  • Only digits are allowed (0-9), which is a small character set. This allows us to optimize using frequency arrays or prefix/suffix counting.
  • Edge cases to watch out for include strings shorter than 5 (where the answer is 0), strings with repeated identical digits (which can form multiple palindromes), and strings with no palindromes at all.

Approaches

Brute-Force Approach: Enumerate all combinations of 5 indices from the string and check if the selected characters form a palindrome. This works correctly but is extremely slow because choosing 5 indices from n has O(n^5) complexity, which is infeasible for n = 10,000.

Optimal Approach: The key insight is that a palindromic subsequence of length 5 has the form a b c b a. This means the first and last characters must be the same, the second and fourth must be the same, and the middle character can be any digit. We can optimize by counting pairs of digits efficiently using prefix and suffix frequency arrays.

  1. Precompute the count of single digits and pairs of digits from left and right.
  2. Iterate over all possible middle positions i for the palindrome. For each position, count how many valid a b pairs exist on the left and right.
  3. Multiply the number of left pairs by the number of right pairs for each i and sum to get the total.
Approach Time Complexity Space Complexity Notes
Brute Force O(n^5) O(1) Enumerate all 5-length subsequences and check palindromicity
Optimal O(n * 100) ≈ O(n) O(100) Count pairs using prefix and suffix frequency arrays for each middle position

Algorithm Walkthrough

  1. Initialize two 2D arrays left and right of size 10 x 10 to store counts of digit pairs (a, b) to the left and right of each position.
  2. Initialize freqLeft and freqRight arrays of size 10 to store counts of single digits to the left and right.
  3. Fill right by iterating from the end of the string to the beginning. For each character, update right using the frequency of digits seen so far on the right. Increment the count for each (current_digit, other_digit) pair. Update freqRight accordingly.
  4. Iterate from left to right. For each position i as the middle character of the palindrome, multiply the count of pairs (a, b) to the left by the count of pairs (a, b) to the right to get the number of palindromes centered at i. Accumulate this count.
  5. Update freqLeft and left arrays for the next iteration.

Why it works: By precomputing the number of valid (a, b) pairs to the left and right of each potential middle character, we ensure that every valid palindrome a b c b a is counted exactly once. The use of prefix and suffix frequency arrays guarantees correctness.

Python Solution

class Solution:
    def countPalindromes(self, s: str) -> int:
        MOD = 10**9 + 7
        n = len(s)
        if n < 5:
            return 0

        left = [[0]*10 for _ in range(10)]
        right = [[0]*10 for _ in range(10)]
        freqLeft = [0]*10
        freqRight = [0]*10

        # Fill right pair counts
        for ch in s:
            d = int(ch)
            for i in range(10):
                right[i][d] += freqRight[i]
            freqRight[d] += 1

        result = 0
        freqLeft = [0]*10

        for ch in s:
            d = int(ch)
            freqRight[d] -= 1
            for i in range(10):
                right[i][d] -= freqRight[i]

            for a in range(10):
                for b in range(10):
                    result = (result + left[a][b] * right[a][b]) % MOD

            for i in range(10):
                left[i][d] += freqLeft[i]
            freqLeft[d] += 1

        return result

The implementation divides the counting into three phases: building the right pairs, iterating through middle positions and combining left and right counts, and updating left pairs. This ensures that all palindromic subsequences are counted efficiently without missing any or double-counting.

Go Solution

func countPalindromes(s string) int {
    const MOD = 1_000_000_007
    n := len(s)
    if n < 5 {
        return 0
    }

    left := [10][10]int{}
    right := [10][10]int{}
    freqLeft := [10]int{}
    freqRight := [10]int{}

    for _, ch := range s {
        d := int(ch - '0')
        for i := 0; i < 10; i++ {
            right[i][d] += freqRight[i]
        }
        freqRight[d]++
    }

    result := 0

    for _, ch := range s {
        d := int(ch - '0')
        freqRight[d]--
        for i := 0; i < 10; i++ {
            right[i][d] -= freqRight[i]
        }

        for a := 0; a < 10; a++ {
            for b := 0; b < 10; b++ {
                result = (result + left[a][b]*right[a][b]) % MOD
            }
        }

        for i := 0; i < 10; i++ {
            left[i][d] += freqLeft[i]
        }
        freqLeft[d]++
    }

    return result
}

The Go version mirrors the Python logic. Arrays are fixed-size for digits 0-9, integer overflow is handled naturally using modulo arithmetic, and type conversion is explicit for character digits.

Worked Examples

Example 1: s = "103301"

  • left pairs after first character: empty.
  • right pairs: counts pairs like (1,0), (0,3), (3,3) etc.
  • Middle character 3: left[a][b] * right[a][b] counts exactly 2 palindromes (10301 twice).

Example 2: s = "0000000"

  • Every combination of 5 zeros forms a palindrome.
  • left and right pair counting ensures all 21 subsequences counted.

Example 3: s = "9999900000"

  • Only palindromes are 99999 and 00000.
  • Counting pairs accurately returns 2.

Complexity Analysis

Measure Complexity Explanation
Time O(n*100) ≈ O(n) Iterate over string for each middle character, nested loop over 10x10 digit pairs
Space O(100) ≈ O(1) Fixed-size arrays for digit pairs and frequencies

The algorithm scales linearly with the string length because the inner loops are constant (10x10), making it efficient for n up to 10,000.

Test Cases

sol = Solution()

# Provided examples
assert sol.countPalindromes("103301") == 2  # Example 1
assert sol.countPalindromes("0000000") == 21  # Example 2
assert sol.countPalindromes("9999900000") == 2  # Example 3

# Boundary cases
assert sol.countPalindromes("") == 0  # Empty string
assert sol.countPalindromes("1234") == 0  # Less than 5 characters
assert sol.countPalindromes("11111") == 1  # Single palindrome of repeated digit
assert sol.countPalindromes("1234512345") > 0  # Multiple palindromes with different digits
Test Why
"" Tests empty input
"1234" Tests input shorter than 5 characters
"11111" Tests input with exactly one palindrome
"103301" Tests example with repeated palindromes
"0000000" Tests repeated identical digit subsequences
"1234512345" Tests