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 Different Palindromic Subsequences

Difficulty: Hard

Problem Description

Given a string s, return the number of different non-empty palindromic subsequences in s. Since the answer may be very large, return it modulo 10^9 + 7. A subsequence of a string is obtained by deleting zero or more characters from the string. A sequence is palindromic if it is equal to the sequence reversed. Two sequences a1, a2, ... and b1, b2, ... are different if there is some i for which ai != bi.

Key Insights

  • A palindromic subsequence reads the same forwards and backwards.
  • Dynamic programming can be used to efficiently count unique palindromic subsequences.
  • Identifying and handling overlapping subsequences is crucial for the correct count.
  • The result must be computed modulo 10^9 + 7 to avoid overflow.

Space and Time Complexity

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

Solution

To solve this problem, we can use a dynamic programming approach. We will maintain a 2D array dp where dp[i][j] represents the count of different palindromic subsequences in the substring s[i...j]. The algorithm can be broken down into the following steps:

  1. Initialization: For every single character in the string, initialize dp[i][i] to 1 since each character is a palindromic subsequence by itself.
  2. Filling the DP Table:
    • For each length of the substring from 2 to n, iterate through all possible starting indices.
    • If the characters at the two ends of the substring are the same, we can form new palindromic subsequences by considering the subsequences formed by the inner substring plus the new palindromic sequences formed by these two characters.
    • If the characters are different, we will count the unique subsequences from both sides, subtracting the overlapping subsequences to avoid double counting.
  3. Result: The value at dp[0][n-1] will give the count of different palindromic subsequences for the entire string.

Code Solutions

def countPalindromicSubsequences(s: str) -> int:
    MOD = 10**9 + 7
    n = len(s)
    dp = [[0] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = 1  # Single character is a palindrome

    for length in range(2, n + 1):  # length of substring
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                low, high = i + 1, j - 1
                while low <= high and s[low] != s[i]:
                    low += 1
                while low <= high and s[high] != s[j]:
                    high -= 1

                if low > high:  # No same characters in between
                    dp[i][j] = dp[i + 1][j - 1] * 2 + 2
                elif low == high:  # One same character in between
                    dp[i][j] = dp[i + 1][j - 1] * 2 + 1
                else:  # More than one same character in between
                    dp[i][j] = dp[i + 1][j - 1] * 2 - dp[low + 1][high - 1]

            else:
                dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]

            dp[i][j] = (dp[i][j] + MOD) % MOD

    return dp[0][n - 1]
← Back to All Questions