Jobs

Interviews

Discussions

Count Different Palindromic Subsequences

Hard

Asked by:

16 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⁹ + 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 a₁, a₂, ... and b₁, b₂, ... are different if there is some i for which a_i != b_i.

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⁹ + 7.

Constraints:

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

Count Different Palindromic Subsequences

Hard

Asked by:

16 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⁹ + 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 a₁, a₂, ... and b₁, b₂, ... are different if there is some i for which a_i != b_i.

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⁹ + 7.

Constraints:

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string, and what characters can it contain?
Is a single character considered a palindromic subsequence?
If no palindromic subsequences exist, what should the function return?
Is the empty string a valid palindromic subsequence, and should it be counted?
Are overlapping subsequences counted as distinct, or should each distinct sequence be counted only once?

Brute Force Solution

Approach

The brute force way to count palindromic subsequences is to explore every possible subsequence of the given string. Then, we check each subsequence to see if it is a palindrome and if we have counted it before. Finally, we tally up the count of distinct palindromic subsequences.

Here's how the algorithm would work step-by-step:

First, generate every possible subsequence of the given string. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
For each subsequence that you generate, check if it is a palindrome. A palindrome reads the same forwards and backward.
If a subsequence is a palindrome, check if you have already counted it. We want to only count distinct palindromic subsequences.
If the palindromic subsequence is new, add it to your count.
Continue generating subsequences, checking for palindromes, and adding to the count until you have explored all possibilities.
The final count represents the number of different palindromic subsequences in the original string.

Code Implementation

def count_different_palindromic_subsequences_brute_force(input_string):
    all_subsequences = set()

    def generate_subsequences(current_index, current_subsequence):
        if current_index == len(input_string):
            if current_subsequence:
                all_subsequences.add(current_subsequence)
            return

        # Include the current character in the subsequence
        generate_subsequences(current_index + 1, current_subsequence + input_string[current_index])

        # Exclude the current character from the subsequence
        generate_subsequences(current_index + 1, current_subsequence)

    generate_subsequences(0, "")
    
    distinct_palindromic_subsequences_count = 0
    palindromes = set()

    for subsequence in all_subsequences:
        # Check if the subsequence is a palindrome
        if subsequence == subsequence[::-1]:

            # Only count distinct palindromes
            if subsequence not in palindromes:

                palindromes.add(subsequence)
                distinct_palindromic_subsequences_count += 1

    return distinct_palindromic_subsequences_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n * n) – Generating all possible subsequences of a string of length n takes O(2^n) time because each character can either be included or excluded in a subsequence. For each subsequence, checking if it is a palindrome takes O(n) time in the worst case, as we may need to compare all characters of the subsequence. Therefore, the overall time complexity is O(2^n * n) since we do the palindrome check for each of the 2^n subsequences. Checking for duplicates could potentially add more to the operations count, but since it is dominated by the subsequence generation and palindrome check, we can ignore it for Big O notation.

Space Complexity

O(2^N + K) – The algorithm generates every possible subsequence of the string, and in the worst case, there are 2^N subsequences, where N is the length of the input string. These subsequences are temporarily stored, implying auxiliary space proportional to 2^N. In addition, to avoid counting duplicate palindromic subsequences, the algorithm must keep track of subsequences it has already counted by using a data structure such as a set which in the worst case could store K unique palindromic subsequences. Therefore the overall space complexity is O(2^N + K).

Optimal Solution

Approach

The key to solving this problem efficiently is to use dynamic programming to avoid recomputing the same subsequences. We'll build a table that stores the number of distinct palindromic subsequences for every possible substring of the given string. We'll fill the table using a bottom-up approach, working from smaller substrings to larger ones.

Here's how the algorithm would work step-by-step:

Imagine we have a table where each cell represents a small part of the whole word, specifically a section starting at one point and ending at another.
We're going to fill this table up by starting with the smallest sections (just one letter), and figure out how many unique palindromes can be made from that small part.
Then we move to slightly larger sections, building on what we already know from the smaller sections. For example, if the start and end letters of a section are the same, then we can easily make longer palindromes by adding these letters to any existing palindromes in the middle section.
If the start and end letters are different, things get a bit trickier, but we still use information from smaller sections to figure out the total count, avoiding counting duplicates.
As we fill up the table, we remember to use a special trick to prevent the numbers from getting too big, which is known as modulo operation.
Finally, the answer we want (the total number of unique palindromes in the whole word) will be in the cell that represents the entire string.

Code Implementation

def count_palindromic_subsequences(input_string):
    string_length = len(input_string)
    dp_table = [[0] * string_length for _ in range(string_length)]
    modulo_value = 10**9 + 7

    for i in range(string_length):
        dp_table[i][i] = 1

    for subsequence_length in range(2, string_length + 1):
        for i in range(string_length - subsequence_length + 1):
            j = i + subsequence_length - 1

            if input_string[i] == input_string[j]:
                # Add the inner subsequence count.
                dp_table[i][j] = 2 * dp_table[i+1][j-1] % modulo_value
                left = i + 1
                right = j - 1

                # Remove duplicate palindromes if any.
                while left <= right and input_string[left] != input_string[i]:
                    left += 1

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

                if left > right:
                    #No duplicates, add 2 for single char and combined.
                    dp_table[i][j] += 2
                elif left == right:
                    # One duplicate.
                    dp_table[i][j] += 1
                else:
                    # Subtract the middle subsequence count.
                    dp_table[i][j] -= dp_table[left+1][right-1]
            else:
                # Remove common subsequences to prevent double-counting.
                dp_table[i][j] = (dp_table[i+1][j] + dp_table[i][j-1] - dp_table[i+1][j-1]) % modulo_value

            dp_table[i][j] = (dp_table[i][j] + modulo_value) % modulo_value

    # Result contains the total number of palindromes.
    return dp_table[0][string_length-1]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The dynamic programming solution involves filling a table where rows and columns represent the start and end indices of substrings within the input string of length n. We iterate through all possible substrings, which requires a nested loop: the outer loop iterates from substring length 1 to n, and the inner loop iterates through all possible starting positions for a given substring length. Calculating the number of distinct palindromic subsequences for each substring requires a constant amount of work. Therefore, the time complexity is dominated by the nested loops that iterate over all substrings, leading to approximately n * n operations, which simplifies to O(n²).

Space Complexity

O(N^2) – The algorithm uses a table (dynamic programming table) to store the number of distinct palindromic subsequences for every possible substring of the given string. This table has dimensions N x N, where N is the length of the input string. Therefore, the auxiliary space required to store this table is proportional to N^2. No other significant auxiliary space is used beyond this table, so the overall space complexity is O(N^2).

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 as there are no palindromic subsequences in an empty string.
Input string of length 1	Return 1 as a single character is a palindrome.
Input string with all identical characters (e.g., 'aaaa')	The number of distinct palindromic subsequences is n+1, where n is the count of that character.
Input string with maximum allowed length	Ensure dynamic programming table doesn't exceed memory limits, consider modulo operation to prevent integer overflow during calculation.
Input string containing only two distinct characters (e.g., 'abab')	This case requires careful handling of overlapping palindromic subsequences.
Integer overflow when calculating the count of palindromic subsequences	Apply modulo operation with a large prime number during the recurrence relation to prevent overflow.
Very long string with many repeating subsequences	The dynamic programming approach efficiently handles repeating subsequences due to its memoization.
String contains unicode characters	Ensure that the character comparison and indexing work correctly with Unicode.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string, and what characters can it contain?
Is a single character considered a palindromic subsequence?
If no palindromic subsequences exist, what should the function return?
Is the empty string a valid palindromic subsequence, and should it be counted?
Are overlapping subsequences counted as distinct, or should each distinct sequence be counted only once?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, generate every possible subsequence of the given string. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
For each subsequence that you generate, check if it is a palindrome. A palindrome reads the same forwards and backward.
If a subsequence is a palindrome, check if you have already counted it. We want to only count distinct palindromic subsequences.
If the palindromic subsequence is new, add it to your count.
Continue generating subsequences, checking for palindromes, and adding to the count until you have explored all possibilities.
The final count represents the number of different palindromic subsequences in the original string.

Code Implementation

def count_different_palindromic_subsequences_brute_force(input_string):
    all_subsequences = set()

    def generate_subsequences(current_index, current_subsequence):
        if current_index == len(input_string):
            if current_subsequence:
                all_subsequences.add(current_subsequence)
            return

        # Include the current character in the subsequence
        generate_subsequences(current_index + 1, current_subsequence + input_string[current_index])

        # Exclude the current character from the subsequence
        generate_subsequences(current_index + 1, current_subsequence)

    generate_subsequences(0, "")
    
    distinct_palindromic_subsequences_count = 0
    palindromes = set()

    for subsequence in all_subsequences:
        # Check if the subsequence is a palindrome
        if subsequence == subsequence[::-1]:

            # Only count distinct palindromes
            if subsequence not in palindromes:

                palindromes.add(subsequence)
                distinct_palindromic_subsequences_count += 1

    return distinct_palindromic_subsequences_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine we have a table where each cell represents a small part of the whole word, specifically a section starting at one point and ending at another.
We're going to fill this table up by starting with the smallest sections (just one letter), and figure out how many unique palindromes can be made from that small part.
Then we move to slightly larger sections, building on what we already know from the smaller sections. For example, if the start and end letters of a section are the same, then we can easily make longer palindromes by adding these letters to any existing palindromes in the middle section.
If the start and end letters are different, things get a bit trickier, but we still use information from smaller sections to figure out the total count, avoiding counting duplicates.
As we fill up the table, we remember to use a special trick to prevent the numbers from getting too big, which is known as modulo operation.
Finally, the answer we want (the total number of unique palindromes in the whole word) will be in the cell that represents the entire string.

Code Implementation

def count_palindromic_subsequences(input_string):
    string_length = len(input_string)
    dp_table = [[0] * string_length for _ in range(string_length)]
    modulo_value = 10**9 + 7

    for i in range(string_length):
        dp_table[i][i] = 1

    for subsequence_length in range(2, string_length + 1):
        for i in range(string_length - subsequence_length + 1):
            j = i + subsequence_length - 1

            if input_string[i] == input_string[j]:
                # Add the inner subsequence count.
                dp_table[i][j] = 2 * dp_table[i+1][j-1] % modulo_value
                left = i + 1
                right = j - 1

                # Remove duplicate palindromes if any.
                while left <= right and input_string[left] != input_string[i]:
                    left += 1

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

                if left > right:
                    #No duplicates, add 2 for single char and combined.
                    dp_table[i][j] += 2
                elif left == right:
                    # One duplicate.
                    dp_table[i][j] += 1
                else:
                    # Subtract the middle subsequence count.
                    dp_table[i][j] -= dp_table[left+1][right-1]
            else:
                # Remove common subsequences to prevent double-counting.
                dp_table[i][j] = (dp_table[i+1][j] + dp_table[i][j-1] - dp_table[i+1][j-1]) % modulo_value

            dp_table[i][j] = (dp_table[i][j] + modulo_value) % modulo_value

    # Result contains the total number of palindromes.
    return dp_table[0][string_length-1]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 as there are no palindromic subsequences in an empty string.
Input string of length 1	Return 1 as a single character is a palindrome.
Input string with all identical characters (e.g., 'aaaa')	The number of distinct palindromic subsequences is n+1, where n is the count of that character.
Input string with maximum allowed length	Ensure dynamic programming table doesn't exceed memory limits, consider modulo operation to prevent integer overflow during calculation.
Input string containing only two distinct characters (e.g., 'abab')	This case requires careful handling of overlapping palindromic subsequences.
Integer overflow when calculating the count of palindromic subsequences	Apply modulo operation with a large prime number during the recurrence relation to prevent overflow.
Very long string with many repeating subsequences	The dynamic programming approach efficiently handles repeating subsequences due to its memoization.
String contains unicode characters	Ensure that the character comparison and indexing work correctly with Unicode.