We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Palindromic Subsequences

Difficulty: Hard

Problem Description

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^9 + 7.

Key Insights

  • A string is palindromic if it reads the same forward and backward.
  • A subsequence is derived from a string by deleting some or no characters without changing the order of the remaining characters.
  • To form a palindromic subsequence of length 5, the first and last characters must be the same, and the middle three characters can vary.
  • The problem involves counting combinations efficiently, especially with potential duplicate digits.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

The solution involves using a dynamic programming approach to count the occurrences of each digit in the string. The idea is to iterate over pairs of indices in the string representing the first and last characters of the palindromic subsequence. For each pair, we count the number of valid combinations of the three middle characters that can be formed from the remaining characters. We maintain a count of occurrences of each digit to facilitate quick calculations. Finally, we return the total count modulo 10^9 + 7.

Code Solutions

def countPalindromicSubseq(s: str) -> int:
    MOD = 10**9 + 7
    n = len(s)
    
    # Count of palindromic subsequences of length 5
    count = 0
    
    # Dictionary to track the frequency of each digit
    freq = {}
    
    # Fill frequency dictionary
    for char in s:
        if char in freq:
            freq[char] += 1
        else:
            freq[char] = 1
            
    # Iterate through each pair of characters
    for i in range(n):
        for j in range(i + 4, n):
            if s[i] == s[j]:  # First and last characters must match
                # Count the characters between i and j
                middle_count = 0
                for k in range(i + 1, j):
                    if s[k] == s[i]:
                        middle_count += 1
                
                # Each middle character can either be included or not
                count += (middle_count + 1) * (middle_count + 1)  # (m + 1) for each middle character
                
                count %= MOD
    
    return count
← Back to All Questions