Taro Logo

Count Different Palindromic Subsequences

Hard
Amazon logo
Amazon
0 views
Topics:
StringsDynamic Programming

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.

Example 1:

Input: s = "bccb" Output: 6 Explanation: The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'. Note that 'bcb' is counted only once, even though it occurs twice.

Example 2:

Input: s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba" Output: 104860361 Explanation: There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 10^9 + 7.

Constraints:

  • 1 <= s.length <= 1000
  • s[i] is either 'a', 'b', 'c', or 'd'.

Solution


Brute Force Approach

A brute force approach would involve generating all possible subsequences of the input string s, checking if each subsequence is a palindrome, and then counting the distinct palindromic subsequences. This approach is highly inefficient due to the exponential number of subsequences a string can have.

  • Time Complexity: O(2n * n), where n is the length of the string. Generating all subsequences takes O(2n) time, and checking if a subsequence is a palindrome takes O(n) time.
  • Space Complexity: O(n), for storing the subsequences.

Optimal Solution: Dynamic Programming

A more efficient approach involves using dynamic programming. We can define dp[i][j] as the number of distinct palindromic subsequences in the substring s[i...j]. The base cases are when i > j, dp[i][j] = 0, and when i == j, dp[i][j] = 1 (a single character is a palindrome).

The recurrence relation is as follows:

  1. If s[i] != s[j], then dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]. We subtract dp[i+1][j-1] to avoid double-counting the palindromic subsequences in s[i+1...j-1].
  2. If s[i] == s[j], we need to consider the characters between i and j:
    • If there are no matching characters between i and j, then dp[i][j] = 2 * dp[i+1][j-1] + 2. The 2 * dp[i+1][j-1] accounts for all palindromic subsequences in s[i+1...j-1] with the outer characters s[i] and s[j] added, and the + 2 accounts for the single character s[i] and the two-character palindrome s[i]s[j].
    • If there is one matching character between i and j at index l, then dp[i][j] = 2 * dp[i+1][j-1] + 1. The + 1 accounts for the single character s[i] which is the same as s[l].
    • If there are more than one matching characters between i and j, let the leftmost be at index l and the rightmost be at index r, then dp[i][j] = 2 * dp[i+1][j-1] - dp[l+1][r-1]. We subtract dp[l+1][r-1] because the palindromic subsequences in s[l+1...r-1] were double-counted.

We need to apply modulo 10^9 + 7 during each calculation to prevent integer overflow.

  • Time Complexity: O(n2), where n is the length of the string, due to the nested loops to fill the DP table.
  • Space Complexity: O(n2), for storing the DP table.

Edge Cases

  • Empty string: The number of distinct non-empty palindromic subsequences is 0.
  • String with one character: The number of distinct non-empty palindromic subsequences is 1.
  • String with all same characters (e.g., "aaaa"): The number of distinct non-empty palindromic subsequences is the length of the string.

Code (Python)

def count_palindromic_subsequences(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    mod = 10**9 + 7

    for i in range(n):
        dp[i][i] = 1

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                l = i + 1
                r = j - 1

                while l <= r and s[l] != s[i]:
                    l += 1
                while l <= r and s[r] != s[i]:
                    r -= 1

                if l > r:
                    dp[i][j] = (2 * dp[i + 1][j - 1] + 2) % mod
                elif l == r:
                    dp[i][j] = (2 * dp[i + 1][j - 1] + 1) % mod
                else:
                    dp[i][j] = (2 * dp[i + 1][j - 1] - dp[l + 1][r - 1]) % mod
                    if dp[i][j] < 0:
                        dp[i][j] += mod

            else:
                dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]) % mod
                if dp[i][j] < 0:
                    dp[i][j] += mod

    return dp[0][n - 1]