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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Different Palindromic Subsequences

Number: 730

Difficulty: Hard

Paid? No

Companies: Uber, LinkedIn

Problem Description

Given a string s that only contains the characters 'a', 'b', 'c', and 'd', find the number of different non-empty palindromic subsequences in s. A subsequence is formed by deleting zero or more characters without changing the relative order, and a palindromic sequence reads the same forwards and backwards. The answer should be returned modulo 10^9 + 7.

Key Insights

  • Use dynamic programming (DP) to count palindromic subsequences in a substring.
  • Define dp[i][j] as the count of distinct palindromic subsequences in the substring s[i...j].
  • For each character (from the set {'a', 'b', 'c', 'd'}), find its first and last occurrence within the current substring.
  • If a character does not exist in the interval, it does not contribute.
  • If the character exists only once (first occurrence equals last occurrence), it contributes one subsequence.
  • If it appears at least twice, it contributes additional palindromic subsequences that can be built by including that character at both ends plus all distinct palindromes within the inner substring.
  • Use recursion with memoization (or iterative DP) to avoid redundant work.
  • Be cautious with adding values and applying the modulo at every step to prevent overflow.

Space and Time Complexity

Time Complexity: O(n^2) where n is the length of the string, since we may need to process all possible substrings. Space Complexity: O(n^2) for storing the DP table and memoization.

Solution

We solve the problem using dynamic programming by considering each interval [i, j] and processing contributions from each of the four possible characters. For each character:

  1. Find the first occurrence index "left" in the interval.
  2. Find the last occurrence index "right" in the interval.
  3. If the character does not appear in the interval, continue.
  4. If the character appears only once (left == right), add 1 to the result.
  5. If the character appears at least twice, add 2 plus the number of distinct palindromic subsequences within the subinterval [left + 1, right - 1]. Recursively compute and cache the results for intervals and combine them, ensuring the result is taken modulo 10^9+7.

Code Solutions

MOD = 10**9 + 7

def countPalindromicSubsequences(s: str) -> int:
    n = len(s)
    # Use memoization for dp(i, j)
    memo = [[-1] * n for _ in range(n)]
    
    def dp(i, j):
        # If invalid range, return 0.
        if i > j:
            return 0
        # If already computed, return it.
        if memo[i][j] != -1:
            return memo[i][j]
        
        ans = 0
        
        # Process each character since only 'a', 'b', 'c', 'd'
        for char in "abcd":
            left = i
            right = j
            # Find the first occurrence of char in s[i...j]
            while left <= j and s[left] != char:
                left += 1
            # If char not present in the interval.
            if left > j:
                continue
            # Find the last occurrence of char in s[i...j]
            while right >= i and s[right] != char:
                right -= 1
            
            if left == right:
                # Only one occurrence: one palindrome "char"
                ans += 1
            else:
                # Two occurrences: add "char" and "char...char" and all palindromes inside
                ans += 2 + dp(left + 1, right - 1)
            ans %= MOD
        
        memo[i][j] = ans
        return ans
    
    return dp(0, n - 1)

# Example usage:
print(countPalindromicSubsequences("bccb"))
← Back to All Questions