Jobs

Interviews

Discussions

Maximum Number of Subsequences After One Inserting

Medium

DE Shaw

3 views

Topics:

ArraysStringsGreedy Algorithms

You are given a string s consisting of uppercase English letters.

You are allowed to insert at most one uppercase English letter at any position (including the beginning or end) of the string.

Return the maximum number of "LCT" subsequences that can be formed in the resulting string after at most one insertion.

Example 1:

Input: s = "LMCT"

Output: 2

Explanation:

We can insert a "L" at the beginning of the string s to make "LLMCT", which has 2 subsequences, at indices [0, 3, 4] and [1, 3, 4].

Example 2:

Input: s = "LCCT"

Output: 4

Explanation:

We can insert a "L" at the beginning of the string s to make "LLCCT", which has 4 subsequences, at indices [0, 2, 4], [0, 3, 4], [1, 2, 4] and [1, 3, 4].

Example 3:

Input: s = "L"

Output: 0

Explanation:

Since it is not possible to obtain the subsequence "LCT" by inserting a single letter, the result is 0.

Constraints:

1 <= s.length <= 10⁵
s consists of uppercase English letters.

Maximum Number of Subsequences After One Inserting

Medium

DE Shaw

3 views

Topics:

ArraysStringsGreedy Algorithms

You are given a string s consisting of uppercase English letters.

You are allowed to insert at most one uppercase English letter at any position (including the beginning or end) of the string.

Return the maximum number of "LCT" subsequences that can be formed in the resulting string after at most one insertion.

Example 1:

Input: s = "LMCT"

Output: 2

Explanation:

We can insert a "L" at the beginning of the string s to make "LLMCT", which has 2 subsequences, at indices [0, 3, 4] and [1, 3, 4].

Example 2:

Input: s = "LCCT"

Output: 4

Explanation:

We can insert a "L" at the beginning of the string s to make "LLCCT", which has 4 subsequences, at indices [0, 2, 4], [0, 3, 4], [1, 2, 4] and [1, 3, 4].

Example 3:

Input: s = "L"

Output: 0

Explanation:

Since it is not possible to obtain the subsequence "LCT" by inserting a single letter, the result is 0.

Constraints:

1 <= s.length <= 10⁵
s consists of uppercase 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 are the maximum lengths of the `text` and `pattern` strings?
Can the `text` or `pattern` strings be empty or null?
Does the `pattern` string consist of distinct characters, or can the same character appear multiple times in the pattern?
If the `pattern` string contains the same character multiple times, how do I handle the counting of subsequences?
If the pattern does not appear at all in the original text, what is the expected return value after inserting the character?

Brute Force Solution

Approach

The problem asks to find the most occurrences of a given subsequence after inserting one character into a string. A brute-force method involves trying every possible insertion point for the character and counting the subsequence occurrences for each.

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

First, think about all the places you could put the extra character inside the original string. That means inserting it before the first character, between every pair of characters, and after the last character.
For each of these new strings with the inserted character, count how many times the subsequence appears.
To count, start from the beginning of both the new string and the subsequence.
If the first characters match, move to the next character in both the string and the subsequence.
If they don't match, move to the next character in the string, but stay on the same character in the subsequence.
Continue until either you've reached the end of the new string or the end of the subsequence.
If you reach the end of the subsequence, that means you've found one occurrence, so increase your count.
After trying all possible insertion positions, compare the counts and pick the highest one.

Code Implementation

def max_subsequence_after_insert(original_string, subsequence):
    max_count = 0
    for insert_index in range(len(original_string) + 1):
        modified_string = original_string[:insert_index] + 'a' + original_string[insert_index:]
        
        subsequence_count = 0
        string_index = 0
        subsequence_index = 0

        # Iterate while there are characters in both strings
        while string_index < len(modified_string) and subsequence_index < len(subsequence):

            if modified_string[string_index] == subsequence[subsequence_index]:
                string_index += 1
                subsequence_index += 1
            else:
                string_index += 1

        # Found one occurrence of the subsequence
        if subsequence_index == len(subsequence):
            subsequence_count += 1
        
        # Keep track of the highest subsequence count
        if subsequence_count > max_count:
            max_count = subsequence_count

    return max_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through n+1 possible insertion points for the new character, where n is the length of the input string. For each insertion, it counts the occurrences of the subsequence. The subsequence counting involves iterating through the modified string (length n+1) and the subsequence (length m). In the worst case, counting occurrences takes O(n*m) time. Because m is constant (the subsequence's length), the subsequence counting takes O(n) time. Since we repeat this O(n) operation for each of the n+1 insertion positions, the total time complexity becomes O(n * n), which simplifies to O(n²).

Space Complexity

O(1) – The provided brute-force algorithm, after inserting a character, counts the subsequence occurrences. The subsequence counting process involves iterating through the new string and the subsequence using index variables. These index variables require constant extra space regardless of the size of the input string or subsequence. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The key to this problem is to efficiently count subsequences by inserting a new character in a smart place. We can do this by counting how many subsequences already exist and then calculating the increase based on where the new character is inserted.

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

First, count how many of the specific subsequence we are looking for exist in the original string. This will be our baseline.
Imagine inserting the new character at every possible spot in the string, including before the first character and after the last.
For each insertion spot, figure out how many new subsequences would be created.
The trick here is recognizing that the new subsequences are created by pairing the newly inserted character with all possible combinations of the subsequence's original characters before and after the insertion point.
To efficiently determine the number of new subsequences formed at each insertion point, keep track of the counts of the first character of the subsequence appearing *before* the insertion point and the counts of the second character appearing *after* the insertion point.
Multiply the count of the first character before the insertion by the count of the second character after the insertion. This gives the number of new subsequences formed if we put the character there.
Repeat for every possible insertion point.
Finally, add the largest number of new subsequences created to the original count. This gives you the maximum number of subsequences possible after one insertion.

Code Implementation

def maximum_subsequence_count(text, pattern):
    first_char = pattern[0]
    second_char = pattern[1]
    text_length = len(text)

    original_count = 0
    first_count = 0

    # First count the existing subsequences.
    for i in range(text_length):
        if text[i] == first_char:
            first_count += 1
        elif text[i] == second_char:
            original_count += first_count

    max_new_subsequences = 0

    # Iterate through possible insertion points
    for i in range(text_length + 1):
        before_first = 0
        after_second = 0
        
        # Count chars before insertion point
        for j in range(i):
            if text[j] == first_char:
                before_first += 1

        # Count chars after insertion point.
        for j in range(i, text_length):
            if text[j] == second_char:
                after_second += 1
        
        # Inserting first char
        if first_char != second_char:
            new_subsequences = after_second
        else:
            new_subsequences = before_first + after_second

        # Find the max subsequences possible
        max_new_subsequences = max(max_new_subsequences, new_subsequences)
        
        before_first = 0
        after_second = 0
        
        # Count chars before insertion point
        for j in range(i):
            if text[j] == first_char:
                before_first += 1

        # Count chars after insertion point.
        for j in range(i, text_length):
            if text[j] == second_char:
                after_second += 1
                
        # Inserting second char
        if first_char != second_char:
            new_subsequences = before_first
        else:
             new_subsequences = before_first + after_second
        
        # Comparing inserting first or second char
        max_new_subsequences = max(max_new_subsequences, new_subsequences)

    # Add existing and maximum
    return original_count + max_new_subsequences

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the string to count the initial number of subsequences. Then, it iterates through the string again to simulate inserting the character at each possible position. Inside this loop, it calculates new subsequences by counting characters before and after the insertion point. These counts are calculated within the same loop iteration, resulting in a single pass through the string. Therefore, the time complexity is directly proportional to the length of the string (n), making it O(n).

Space Complexity

O(1) – The provided solution primarily utilizes a few integer variables to store counts of the first character before the insertion point and the second character after the insertion point. These variables consume constant space regardless of the input string's length (N). No auxiliary data structures that scale with the input size are used. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
text or pattern is null	Throw IllegalArgumentException or return 0 if null is not allowed by problem statement.
text or pattern is empty string	If pattern is empty return 0. If text is empty, return 1 if pattern's length is 1, otherwise 0.
pattern length is greater than text length + 1	Return 0, since pattern can never be a subsequence after inserting just one character.
text length is very large, causing potential integer overflow in counting subsequences	Use long data type to store the number of subsequences.
pattern contains characters not present in text	The algorithm should correctly count subsequences regardless of the absence of pattern characters in text.
pattern has repeated characters (e.g., 'aaa')	The algorithm must handle repeated characters in the pattern correctly when counting subsequences.
The first character of pattern appears very frequently in text, leading to many potential insertion locations	The algorithm must iterate efficiently, avoiding redundant calculations when many insertion points exist.
Inserting the pattern's first character at multiple locations yields the same maximum number of subsequences	Return any one of these maximum results as specified by the question.

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 are the maximum lengths of the `text` and `pattern` strings?
Can the `text` or `pattern` strings be empty or null?
Does the `pattern` string consist of distinct characters, or can the same character appear multiple times in the pattern?
If the `pattern` string contains the same character multiple times, how do I handle the counting of subsequences?
If the pattern does not appear at all in the original text, what is the expected return value after inserting the character?

Brute Force Solution

Approach

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

First, think about all the places you could put the extra character inside the original string. That means inserting it before the first character, between every pair of characters, and after the last character.
For each of these new strings with the inserted character, count how many times the subsequence appears.
To count, start from the beginning of both the new string and the subsequence.
If the first characters match, move to the next character in both the string and the subsequence.
If they don't match, move to the next character in the string, but stay on the same character in the subsequence.
Continue until either you've reached the end of the new string or the end of the subsequence.
If you reach the end of the subsequence, that means you've found one occurrence, so increase your count.
After trying all possible insertion positions, compare the counts and pick the highest one.

Code Implementation

def max_subsequence_after_insert(original_string, subsequence):
    max_count = 0
    for insert_index in range(len(original_string) + 1):
        modified_string = original_string[:insert_index] + 'a' + original_string[insert_index:]
        
        subsequence_count = 0
        string_index = 0
        subsequence_index = 0

        # Iterate while there are characters in both strings
        while string_index < len(modified_string) and subsequence_index < len(subsequence):

            if modified_string[string_index] == subsequence[subsequence_index]:
                string_index += 1
                subsequence_index += 1
            else:
                string_index += 1

        # Found one occurrence of the subsequence
        if subsequence_index == len(subsequence):
            subsequence_count += 1
        
        # Keep track of the highest subsequence count
        if subsequence_count > max_count:
            max_count = subsequence_count

    return max_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:

First, count how many of the specific subsequence we are looking for exist in the original string. This will be our baseline.
Imagine inserting the new character at every possible spot in the string, including before the first character and after the last.
For each insertion spot, figure out how many new subsequences would be created.
The trick here is recognizing that the new subsequences are created by pairing the newly inserted character with all possible combinations of the subsequence's original characters before and after the insertion point.
To efficiently determine the number of new subsequences formed at each insertion point, keep track of the counts of the first character of the subsequence appearing *before* the insertion point and the counts of the second character appearing *after* the insertion point.
Multiply the count of the first character before the insertion by the count of the second character after the insertion. This gives the number of new subsequences formed if we put the character there.
Repeat for every possible insertion point.
Finally, add the largest number of new subsequences created to the original count. This gives you the maximum number of subsequences possible after one insertion.

Code Implementation

def maximum_subsequence_count(text, pattern):
    first_char = pattern[0]
    second_char = pattern[1]
    text_length = len(text)

    original_count = 0
    first_count = 0

    # First count the existing subsequences.
    for i in range(text_length):
        if text[i] == first_char:
            first_count += 1
        elif text[i] == second_char:
            original_count += first_count

    max_new_subsequences = 0

    # Iterate through possible insertion points
    for i in range(text_length + 1):
        before_first = 0
        after_second = 0
        
        # Count chars before insertion point
        for j in range(i):
            if text[j] == first_char:
                before_first += 1

        # Count chars after insertion point.
        for j in range(i, text_length):
            if text[j] == second_char:
                after_second += 1
        
        # Inserting first char
        if first_char != second_char:
            new_subsequences = after_second
        else:
            new_subsequences = before_first + after_second

        # Find the max subsequences possible
        max_new_subsequences = max(max_new_subsequences, new_subsequences)
        
        before_first = 0
        after_second = 0
        
        # Count chars before insertion point
        for j in range(i):
            if text[j] == first_char:
                before_first += 1

        # Count chars after insertion point.
        for j in range(i, text_length):
            if text[j] == second_char:
                after_second += 1
                
        # Inserting second char
        if first_char != second_char:
            new_subsequences = before_first
        else:
             new_subsequences = before_first + after_second
        
        # Comparing inserting first or second char
        max_new_subsequences = max(max_new_subsequences, new_subsequences)

    # Add existing and maximum
    return original_count + max_new_subsequences

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
text or pattern is null	Throw IllegalArgumentException or return 0 if null is not allowed by problem statement.
text or pattern is empty string	If pattern is empty return 0. If text is empty, return 1 if pattern's length is 1, otherwise 0.
pattern length is greater than text length + 1	Return 0, since pattern can never be a subsequence after inserting just one character.
text length is very large, causing potential integer overflow in counting subsequences	Use long data type to store the number of subsequences.
pattern contains characters not present in text	The algorithm should correctly count subsequences regardless of the absence of pattern characters in text.
pattern has repeated characters (e.g., 'aaa')	The algorithm must handle repeated characters in the pattern correctly when counting subsequences.
The first character of pattern appears very frequently in text, leading to many potential insertion locations	The algorithm must iterate efficiently, avoiding redundant calculations when many insertion points exist.
Inserting the pattern's first character at multiple locations yields the same maximum number of subsequences	Return any one of these maximum results as specified by the question.