Jobs

Interviews

Discussions

Count Palindromic Subsequences

Hard

Count Palindromic Subsequences

Hard

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 `s`?
Can the input string `s` contain characters other than lowercase English letters?
Is an empty string a valid input, and if so, what should be the expected output?
Could you clarify what is meant by 'distinct'? For example, if the string is 'aba', are 'a' counted twice, or only once?
What is the expected output if the string contains no palindromic subsequences?

Brute Force Solution

Approach

The brute force method for counting palindromic subsequences involves checking every possible subsequence within the given sequence. We generate all possible subsequences, no matter how short or long, and then check if each of these is a palindrome. Finally, we count only the subsequences that meet the palindrome criteria, avoiding duplicate counts.

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

First, we need to make a list of every possible subsequence you can create from the original sequence. A subsequence is formed by taking some characters from the original sequence, without changing their order, but you don't have to take every character.
Now, go through the entire list of subsequences, one by one.
For each subsequence, we check if it is a palindrome. A palindrome reads the same forwards and backward.
If the subsequence is a palindrome, we add it to a list of palindromic subsequences.
Once you've checked all the subsequences, count how many unique palindromic subsequences you have in your list. Make sure that you only count each palindromic subsequence once.
The final count represents the total number of palindromic subsequences.

Code Implementation

def count_palindromic_subsequences_brute_force(input_sequence):
    all_subsequences = []
    sequence_length = len(input_sequence)

    for i in range(1 << sequence_length):
        subsequence = ""
        for j in range(sequence_length):
            if (i >> j) & 1:
                subsequence += input_sequence[j]
        all_subsequences.append(subsequence)

    palindromic_subsequences = set()

    for subsequence in all_subsequences:
        # Check if the current subsequence is a palindrome.
        if subsequence == subsequence[::-1]:
            # Only add the palindrome to the set if its not already there.
            palindromic_subsequences.add(subsequence)

    # Return the total count of unique palindromic subsequences
    return len(palindromic_subsequences)

Big(O) Analysis

Time Complexity

O(2^n * n) – Generating all possible subsequences of a sequence of length n takes O(2^n) time because each element can either be included or excluded in a subsequence. For each subsequence generated, checking if it is a palindrome takes O(n) time in the worst case, as we might need to compare each character of the subsequence to its counterpart. Therefore, the overall time complexity is O(2^n * n).

Space Complexity

O(2^N + K) – The algorithm generates all possible subsequences, requiring storage for up to 2^N subsequences where N is the length of the input string. It stores these subsequences in a list. Additionally, a list (or set) of size K is used to store the unique palindromic subsequences to avoid duplicates. Therefore, the auxiliary space is O(2^N + K), where K <= 2^N.

Optimal Solution

Approach

To count palindromic subsequences efficiently, we'll use a method that remembers results we've already calculated. This avoids recalculating the same information, making the whole process much faster, particularly for long sequences.

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

Imagine a table where each cell represents whether a specific part of the sequence is a palindrome or not.
Start by filling in the table for the smallest possible subsequences: single characters. Each single character is a palindrome by itself, so mark those accordingly.
Next, consider subsequences with two characters. Check if the two characters are the same. If they are, then it's a palindrome; otherwise, it's not. Record these results.
Now, move on to longer subsequences, building them up one character at a time. For a subsequence to be a palindrome, the first and last characters must be the same, and the remaining inner subsequence must also be a palindrome (which we already know from our table).
If the first and last characters of a subsequence match, add the number of palindromic subsequences of the inner sequence to our count.
If the first and last characters do not match, we take the total count of the two smaller subproblems formed by the subsequence without the first character and the subsequence without the last character, and subtract from it the count of their common subsequence.
By following this approach, we build up our table of palindrome counts from small to large. The final cell in the table will tell us the total number of palindromic subsequences for the entire sequence.

Code Implementation

def count_palindromic_subsequences(input_string):
    string_length = len(input_string)
    
    # Initialize a table to store counts of palindromic subsequences.
    palindrome_counts = [[0] * string_length for _ in range(string_length)]

    # Every single character is a palindrome of length 1.
    for i in range(string_length):
        palindrome_counts[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 the first and last characters match, consider the inner substring.
            if input_string[i] == input_string[j]:
                # Add inner count + the two single char palindromes.
                if subsequence_length == 2:
                    palindrome_counts[i][j] = 2
                else:
                    palindrome_counts[i][j] = (
                        palindrome_counts[i + 1][j - 1] + 2
                    )

            else:
                # If the first and last characters do not match
                # subtract overlapping subproblems
                palindrome_counts[i][j] = (
                    palindrome_counts[i][j - 1]
                    + palindrome_counts[i + 1][j]
                    - palindrome_counts[i + 1][j - 1]
                )

    # The top-right cell contains the final result.
    return palindrome_counts[0][string_length - 1]

Big(O) Analysis

Time Complexity

O(n²) – The algorithm utilizes dynamic programming to count palindromic subsequences. A table of size n x n is constructed, where n is the length of the input sequence. The table is filled in a bottom-up manner, considering subsequences of increasing length. Filling each cell in the table requires constant time operations, involving comparisons and additions. Since we iterate over all possible sub-sequences with two indices i and j from 0 to n, the number of operations will be proportional to n². Thus, the overall time complexity is O(n²).

Space Complexity

O(N^2) – The algorithm uses a table (essentially a 2D array) to store whether a specific part of the sequence is a palindrome or not and to store the count of palindromic subsequences. This table has dimensions N x N, where N is the length of the input sequence. Therefore, the auxiliary space required to store this table is proportional to N^2, dominating the space complexity. The additional single variables used do not significantly contribute to the overall space complexity.

Edge Cases

Case	How to Handle
Empty string s	Return 0, as there are no palindromic subsequences.
String s with a single character	Return 1, as the single character itself is a palindromic subsequence.
String s with two identical characters (e.g., 'aa')	Return 1, as 'a' is a palindrome and 'aa' is also a palindrome - so 2 distinct subsequences.
String s with two different characters (e.g., 'ab')	Return 2, 'a' and 'b' are palindromes.
String s with all identical characters (e.g., 'aaaa')	Return 1, because only one distinct character is present which forms a unique palindromic subsequence.
Very long string s with repeating palindromic subsequences	Dynamic programming with memoization handles overlapping subproblems efficiently to avoid recomputation and ensures the solution scales for long strings.
String s with only two unique characters repeating many times	The DP approach ensures that we are counting distinct subsequences even with repetitions, and handles the potentially large count with modulo operation.
String s that results in a very large number of palindromic subsequences causing integer overflow.	Apply the modulo operator (1000000007) after each calculation to prevent overflow.

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 `s`?
Can the input string `s` contain characters other than lowercase English letters?
Is an empty string a valid input, and if so, what should be the expected output?
Could you clarify what is meant by 'distinct'? For example, if the string is 'aba', are 'a' counted twice, or only once?
What is the expected output if the string contains no palindromic subsequences?

Brute Force Solution

Approach

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

First, we need to make a list of every possible subsequence you can create from the original sequence. A subsequence is formed by taking some characters from the original sequence, without changing their order, but you don't have to take every character.
Now, go through the entire list of subsequences, one by one.
For each subsequence, we check if it is a palindrome. A palindrome reads the same forwards and backward.
If the subsequence is a palindrome, we add it to a list of palindromic subsequences.
Once you've checked all the subsequences, count how many unique palindromic subsequences you have in your list. Make sure that you only count each palindromic subsequence once.
The final count represents the total number of palindromic subsequences.

Code Implementation

def count_palindromic_subsequences_brute_force(input_sequence):
    all_subsequences = []
    sequence_length = len(input_sequence)

    for i in range(1 << sequence_length):
        subsequence = ""
        for j in range(sequence_length):
            if (i >> j) & 1:
                subsequence += input_sequence[j]
        all_subsequences.append(subsequence)

    palindromic_subsequences = set()

    for subsequence in all_subsequences:
        # Check if the current subsequence is a palindrome.
        if subsequence == subsequence[::-1]:
            # Only add the palindrome to the set if its not already there.
            palindromic_subsequences.add(subsequence)

    # Return the total count of unique palindromic subsequences
    return len(palindromic_subsequences)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine a table where each cell represents whether a specific part of the sequence is a palindrome or not.
Start by filling in the table for the smallest possible subsequences: single characters. Each single character is a palindrome by itself, so mark those accordingly.
Next, consider subsequences with two characters. Check if the two characters are the same. If they are, then it's a palindrome; otherwise, it's not. Record these results.
Now, move on to longer subsequences, building them up one character at a time. For a subsequence to be a palindrome, the first and last characters must be the same, and the remaining inner subsequence must also be a palindrome (which we already know from our table).
If the first and last characters of a subsequence match, add the number of palindromic subsequences of the inner sequence to our count.
If the first and last characters do not match, we take the total count of the two smaller subproblems formed by the subsequence without the first character and the subsequence without the last character, and subtract from it the count of their common subsequence.
By following this approach, we build up our table of palindrome counts from small to large. The final cell in the table will tell us the total number of palindromic subsequences for the entire sequence.

Code Implementation

def count_palindromic_subsequences(input_string):
    string_length = len(input_string)
    
    # Initialize a table to store counts of palindromic subsequences.
    palindrome_counts = [[0] * string_length for _ in range(string_length)]

    # Every single character is a palindrome of length 1.
    for i in range(string_length):
        palindrome_counts[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 the first and last characters match, consider the inner substring.
            if input_string[i] == input_string[j]:
                # Add inner count + the two single char palindromes.
                if subsequence_length == 2:
                    palindrome_counts[i][j] = 2
                else:
                    palindrome_counts[i][j] = (
                        palindrome_counts[i + 1][j - 1] + 2
                    )

            else:
                # If the first and last characters do not match
                # subtract overlapping subproblems
                palindrome_counts[i][j] = (
                    palindrome_counts[i][j - 1]
                    + palindrome_counts[i + 1][j]
                    - palindrome_counts[i + 1][j - 1]
                )

    # The top-right cell contains the final result.
    return palindrome_counts[0][string_length - 1]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string s	Return 0, as there are no palindromic subsequences.
String s with a single character	Return 1, as the single character itself is a palindromic subsequence.
String s with two identical characters (e.g., 'aa')	Return 1, as 'a' is a palindrome and 'aa' is also a palindrome - so 2 distinct subsequences.
String s with two different characters (e.g., 'ab')	Return 2, 'a' and 'b' are palindromes.
String s with all identical characters (e.g., 'aaaa')	Return 1, because only one distinct character is present which forms a unique palindromic subsequence.
Very long string s with repeating palindromic subsequences	Dynamic programming with memoization handles overlapping subproblems efficiently to avoid recomputation and ensures the solution scales for long strings.
String s with only two unique characters repeating many times	The DP approach ensures that we are counting distinct subsequences even with repetitions, and handles the potentially large count with modulo operation.
String s that results in a very large number of palindromic subsequences causing integer overflow.	Apply the modulo operator (1000000007) after each calculation to prevent overflow.