Count Different Palindromic Subsequences Interview Question for Amazon

## Different Palindromic Subsequences

### Problem Description

Given a string `s`, the task is to find the number of different non-empty palindromic subsequences in `s`. Since the answer can 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


### Naive Approach

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

```python
def is_palindrome(s):
    return s == s[::-1]

def count_palindromic_subsequences_brute_force(s):
    n = len(s)
    subsequences = set()
    
    for i in range(1 << n):
        subsequence = ""
        for j in range(n):
            if (i >> j) & 1:
                subsequence += s[j]
        
        if subsequence and is_palindrome(subsequence):
            subsequences.add(subsequence)
    
    return len(subsequences) % (10**9 + 7)

# Example usage:
s = "bccb"
print(count_palindromic_subsequences_brute_force(s))

This naive approach generates all possible subsequences and checks each one. This has an exponential time complexity.

Optimal Approach: Dynamic Programming

A more efficient approach is to use dynamic programming. Let dp[i][j] be the number of distinct palindromic subsequences in the substring s[i:j+1]. We can define the following recurrence relation:

If s[i] != s[j], then dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]
If s[i] == s[j], then we need to consider the occurrences of s[i] (or s[j]) in the substring s[i+1:j]. There are three cases:
- If there are no occurrences of s[i] in s[i+1:j], then dp[i][j] = 2 * dp[i+1][j-1] + 2 (we add 2 for the single character s[i] and the subsequence s[i]s[j])
- If there is one occurrence of s[i] at index k in s[i+1:j], then dp[i][j] = 2 * dp[i+1][j-1] + 1 (we add 1 for the subsequence s[i]s[j])
- If there are two or more occurrences of s[i] in s[i+1:j], let left be the index of the first occurrence and right be the index of the last occurrence. Then dp[i][j] = 2 * dp[i+1][j-1] - dp[left+1][right-1]

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]:
                left = i + 1
                right = j - 1

                while left <= right and s[left] != s[i]:
                    left += 1
                while left <= right and s[right] != s[i]:
                    right -= 1

                if left > right:
                    dp[i][j] = (2 * dp[i+1][j-1] + 2) % mod
                elif left == right:
                    dp[i][j] = (2 * dp[i+1][j-1] + 1) % mod
                else:
                    dp[i][j] = (2 * dp[i+1][j-1] - dp[left+1][right-1]) % mod
            else:
                dp[i][j] = (dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]) % mod

            dp[i][j] = (dp[i][j] + mod) % mod  # Ensure non-negative

    return dp[0][n-1]

# Example usage:
s = "bccb"
print(count_palindromic_subsequences(s))

s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"
print(count_palindromic_subsequences(s))

Big(O) Runtime Analysis

The time complexity of the dynamic programming solution is O(n^2), where n is the length of the string s. This is because we have a nested loop that iterates through all possible substrings of s, and the inner while loops (to find left and right) run in O(n) in the worst case, but the amortized time is still O(1). The main dynamic programming part computes dp[i][j] for all i and j, which takes O(n^2).

Big(O) Space Usage Analysis

The space complexity of the dynamic programming solution is O(n^2) because we are using a 2D array dp of size n x n to store the number of distinct palindromic subsequences for each substring.

Edge Cases

Empty String: If the input string s is empty, the number of distinct palindromic subsequences is 0.
Single Character String: If the input string s contains only one character, the number of distinct palindromic subsequences is 1.
String with Identical Characters: If the input string s contains only identical characters (e.g., "aaaa"), the number of distinct palindromic subsequences is equal to the length of the string.
Long Palindromic String: If the input string s is a long palindromic string, the dynamic programming approach will still work efficiently due to its O(n^2) time complexity.
Modulo Operation: To handle the cases where the number of distinct palindromic subsequences is very large, we use the modulo operator % (10**9 + 7) to keep the result within the range of an integer.