Jobs

Interviews

Discussions

Distinct Subsequences II

Hard

Uber

1 view

Topics:

Dynamic Programming

Given a string s, return the number of distinct non-empty subsequences of s. Since the answer may be very large, return it modulo 10^9 + 7.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

For example:

If s = "abc", the output should be 7. The distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".
If s = "aba", the output should be 6. The distinct subsequences are "a", "b", "ab", "aa", "ba", and "aba".
If s = "aaa", the output should be 3. The distinct subsequences are "a", "aa" and "aaa".

Constraints:

1 <= s.length <= 2000
s consists of lowercase English letters.

Distinct Subsequences II

Hard

Uber

1 view

Topics:

Dynamic Programming

Given a string s, return the number of distinct non-empty subsequences of s. Since the answer may be very large, return it modulo 10^9 + 7.

For example:

If s = "abc", the output should be 7. The distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".
If s = "aba", the output should be 6. The distinct subsequences are "a", "b", "ab", "aa", "ba", and "aba".
If s = "aaa", the output should be 3. The distinct subsequences are "a", "aa" and "aaa".

Constraints:

1 <= s.length <= 2000
s consists of lowercase English letters.

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 possible length of the input string s?
Can the input string s contain only lowercase letters, or can it contain other characters (uppercase, numbers, symbols)?
Is an empty string considered a valid subsequence? (The problem states non-empty, but I want to confirm if the empty string should still be excluded from our calculation during intermediate steps.)
Could you provide a small example, such as 'abc', and the expected distinct subsequences, to ensure I understand the definition clearly?
Should the returned number of distinct subsequences be a 32-bit integer, or is there a possibility it could require a 64-bit integer before taking the modulo?

Brute Force Solution

Approach

The brute force approach to finding distinct subsequences involves checking absolutely every possible combination of characters from the input. We essentially create and examine every conceivable subsequence, regardless of its length or content. This ensures that we do not miss any potential solution, even if it's computationally expensive.

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

First, consider an empty sequence, a subsequence with nothing in it. Note it down.
Next, pick the first character of the original string and create a subsequence with just that character. Note this down, unless it's a repeat of a sequence we already have.
Then, pick the second character, create a subsequence with just that character, and note it down if it's new.
Continue this, making single-character subsequences from each character in the original string, skipping duplicates.
Now, consider subsequences of length two. Start with the first two characters. Then, the first and third characters. Then, the first and fourth characters, and so on. Note each down, only if it's a new distinct sequence.
Do the same thing with subsequences of length three, four, and so on, up to the full length of the original string, checking all possible combinations and noting down only the distinct subsequences each time.
Finally, count all the distinct subsequences we have collected. That's our answer.

Code Implementation

def distinct_subsequences_brute_force(input_string):
    distinct_subsequence_set = set()
    distinct_subsequence_set.add('')

    string_length = len(input_string)

    for subsequence_length in range(1, string_length + 1):
        for i in range(1 << string_length):
            if bin(i).count('1') == subsequence_length:
                subsequence = ''
                index = 0

                # Construct the subsequence based on the bitmask
                for j in range(string_length):
                    if (i >> j) & 1:
                        subsequence += input_string[j]
                        index += 1

                # Add the subsequence to the set if it's distinct
                distinct_subsequence_set.add(subsequence)

    # Remove the empty string as requested
    distinct_subsequence_set.remove('')

    return len(distinct_subsequence_set)

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach generates all possible subsequences of the input string of length n. For each character, we have two choices: either include it in the subsequence or exclude it. This leads to 2^n possible subsequences. Checking for distinctness among these subsequences requires comparing each new subsequence with all existing ones which contributes another factor that doesn't change the exponential order. Therefore, the time complexity is O(2^n).

Space Complexity

O(2^N) – The brute force approach, as described, generates and stores every possible subsequence. In the worst-case scenario, each character could be either included or excluded from a subsequence, leading to 2^N possible subsequences, where N is the length of the input string. We are 'noting down' each distinct subsequence, implying storage in a data structure like a set or list. Therefore, the auxiliary space required to store these subsequences grows exponentially with the input size, approximating O(2^N).

Optimal Solution

Approach

To find the number of unique subsequences in a string, we'll build the subsequences character by character. The key idea is to use a mathematical relationship to keep track of the number of distinct subsequences ending with each character we've seen so far.

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

Think of the problem as building up distinct subsequences as you go through the string from left to right.
Start with a count of 1, which represents the empty subsequence.
For each letter in the string, the number of new subsequences we create is equal to the total number of subsequences we had so far.
Add this new count to the total count of subsequences.
If we've seen this letter before, subtract the number of subsequences that ended with that letter from the current total. This is because adding the letter again would create duplicates of these existing subsequences.
Keep track of the number of subsequences that end with each letter.
In the end, subtract 1 from the total count to exclude the empty subsequence.
The result is the number of distinct, non-empty subsequences.

Code Implementation

def distinct_subsequences_two(input_string):
    modulo = 10**9 + 7
    end_with = {}
    total_subsequences = 1

    for char in input_string:
        new_subsequences = total_subsequences

        total_subsequences = (total_subsequences + new_subsequences) % modulo

        # Avoid double counting subsequences
        if char in end_with:
            total_subsequences = (total_subsequences - end_with[char] + modulo) % modulo

        end_with[char] = new_subsequences

    # Remove the empty string from the final count
    return (total_subsequences - 1 + modulo) % modulo

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n once. Inside the loop, the operations performed are constant time operations: updating the total count, adding new subsequences, subtracting duplicates (if the character has been seen before), and updating the count of subsequences ending with the current character. Since the loop iterates n times and the operations inside the loop take constant time, the overall time complexity is O(n).

Space Complexity

O(1) – The algorithm utilizes a dictionary or hash map to keep track of the number of subsequences ending with each letter. The size of this dictionary is bounded by the number of possible characters, which is typically a constant (e.g., 26 for lowercase English letters or 128 for ASCII). Therefore, the space used by this data structure remains constant regardless of the input string's length (N). The algorithm uses a few additional variables to store counts, which also take up constant space. Consequently, the overall space complexity is O(1).

Edge Cases

Case	How to Handle
Empty string input	Return 0 since there are no non-empty subsequences.
String with a single character	Return 1 since the only subsequence is the character itself.
String with all identical characters (e.g., 'aaaa')	The number of distinct subsequences is equal to the character itself, thus return 1.
Maximum length string with distinct characters	Ensure the chosen algorithm can handle the maximum input size efficiently, potentially using dynamic programming to avoid exponential time complexity.
String with mixed case characters (if case sensitivity is an issue)	Clearly define the case sensitivity of the problem (treat 'a' and 'A' as distinct or not) and handle the characters accordingly.
Potential integer overflow when calculating the number of subsequences.	Use the modulo operator (10^9 + 7) during intermediate calculations to prevent integer overflow.
String containing special characters or unicode.	Verify the algorithm correctly handles any valid UTF-8 character, especially if relying on character code offsets for indexing.
Very long string with repeating subsequences (e.g., 'ababababab')	The solution should correctly handle overlapping subsequences and avoid overcounting distinct subsequences using dynamic programming.

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 possible length of the input string s?
Can the input string s contain only lowercase letters, or can it contain other characters (uppercase, numbers, symbols)?
Is an empty string considered a valid subsequence? (The problem states non-empty, but I want to confirm if the empty string should still be excluded from our calculation during intermediate steps.)
Could you provide a small example, such as 'abc', and the expected distinct subsequences, to ensure I understand the definition clearly?
Should the returned number of distinct subsequences be a 32-bit integer, or is there a possibility it could require a 64-bit integer before taking the modulo?

Brute Force Solution

Approach

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

First, consider an empty sequence, a subsequence with nothing in it. Note it down.
Next, pick the first character of the original string and create a subsequence with just that character. Note this down, unless it's a repeat of a sequence we already have.
Then, pick the second character, create a subsequence with just that character, and note it down if it's new.
Continue this, making single-character subsequences from each character in the original string, skipping duplicates.
Now, consider subsequences of length two. Start with the first two characters. Then, the first and third characters. Then, the first and fourth characters, and so on. Note each down, only if it's a new distinct sequence.
Do the same thing with subsequences of length three, four, and so on, up to the full length of the original string, checking all possible combinations and noting down only the distinct subsequences each time.
Finally, count all the distinct subsequences we have collected. That's our answer.

Code Implementation

def distinct_subsequences_brute_force(input_string):
    distinct_subsequence_set = set()
    distinct_subsequence_set.add('')

    string_length = len(input_string)

    for subsequence_length in range(1, string_length + 1):
        for i in range(1 << string_length):
            if bin(i).count('1') == subsequence_length:
                subsequence = ''
                index = 0

                # Construct the subsequence based on the bitmask
                for j in range(string_length):
                    if (i >> j) & 1:
                        subsequence += input_string[j]
                        index += 1

                # Add the subsequence to the set if it's distinct
                distinct_subsequence_set.add(subsequence)

    # Remove the empty string as requested
    distinct_subsequence_set.remove('')

    return len(distinct_subsequence_set)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Think of the problem as building up distinct subsequences as you go through the string from left to right.
Start with a count of 1, which represents the empty subsequence.
For each letter in the string, the number of new subsequences we create is equal to the total number of subsequences we had so far.
Add this new count to the total count of subsequences.
If we've seen this letter before, subtract the number of subsequences that ended with that letter from the current total. This is because adding the letter again would create duplicates of these existing subsequences.
Keep track of the number of subsequences that end with each letter.
In the end, subtract 1 from the total count to exclude the empty subsequence.
The result is the number of distinct, non-empty subsequences.

Code Implementation

def distinct_subsequences_two(input_string):
    modulo = 10**9 + 7
    end_with = {}
    total_subsequences = 1

    for char in input_string:
        new_subsequences = total_subsequences

        total_subsequences = (total_subsequences + new_subsequences) % modulo

        # Avoid double counting subsequences
        if char in end_with:
            total_subsequences = (total_subsequences - end_with[char] + modulo) % modulo

        end_with[char] = new_subsequences

    # Remove the empty string from the final count
    return (total_subsequences - 1 + modulo) % modulo

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string input	Return 0 since there are no non-empty subsequences.
String with a single character	Return 1 since the only subsequence is the character itself.
String with all identical characters (e.g., 'aaaa')	The number of distinct subsequences is equal to the character itself, thus return 1.
Maximum length string with distinct characters	Ensure the chosen algorithm can handle the maximum input size efficiently, potentially using dynamic programming to avoid exponential time complexity.
String with mixed case characters (if case sensitivity is an issue)	Clearly define the case sensitivity of the problem (treat 'a' and 'A' as distinct or not) and handle the characters accordingly.
Potential integer overflow when calculating the number of subsequences.	Use the modulo operator (10^9 + 7) during intermediate calculations to prevent integer overflow.
String containing special characters or unicode.	Verify the algorithm correctly handles any valid UTF-8 character, especially if relying on character code offsets for indexing.
Very long string with repeating subsequences (e.g., 'ababababab')	The solution should correctly handle overlapping subsequences and avoid overcounting distinct subsequences using dynamic programming.