Jobs

Interviews

Discussions

Minimum String Length After Removing Substrings

#887 Most AskedEasy

Minimum String Length After Removing Substrings #887 Most Asked

Easy

Microsoft

4 views

Topics:

StringsStacks

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

You can apply some operations to this string where, in one operation, you can remove any occurrence of one of the substrings "AB" or "CD" from s.

Return the minimum possible length of the resulting string that you can obtain.

Note that the string concatenates after removing the substring and could produce new "AB" or "CD" substrings.

Example 1:

Input: s = "ABFCACDB"
Output: 2
Explanation: We can do the following operations:
- Remove the substring "ABFCACDB", so s = "FCACDB".
- Remove the substring "FCACDB", so s = "FCAB".
- Remove the substring "FCAB", so s = "FC".
So the resulting length of the string is 2.
It can be shown that it is the minimum length that we can obtain.

Example 2:

Input: s = "ACBBD"
Output: 5
Explanation: We cannot do any operations on the string so the length remains the same.

Constraints:

1 <= s.length <= 100
s consists only of uppercase English letters.

Try coding it in LeetCode

Minimum String Length After Removing Substrings

#887 Most AskedEasy

Minimum String Length After Removing Substrings #887 Most Asked

Easy

Microsoft

4 views

Topics:

StringsStacks

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

You can apply some operations to this string where, in one operation, you can remove any occurrence of one of the substrings "AB" or "CD" from s.

Return the minimum possible length of the resulting string that you can obtain.

Note that the string concatenates after removing the substring and could produce new "AB" or "CD" substrings.

Example 1:

Input: s = "ABFCACDB"
Output: 2
Explanation: We can do the following operations:
- Remove the substring "ABFCACDB", so s = "FCACDB".
- Remove the substring "FCACDB", so s = "FCAB".
- Remove the substring "FCAB", so s = "FC".
So the resulting length of the string is 2.
It can be shown that it is the minimum length that we can obtain.

Example 2:

Input: s = "ACBBD"
Output: 5
Explanation: We cannot do any operations on the string so the length remains the same.

Constraints:

1 <= s.length <= 100
s consists only of uppercase English letters.

Try coding it in LeetCode

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 possible substrings that can be removed, and are there any restrictions on the characters that can appear in the initial string?
What is the maximum length of the input string?
If no removals are possible, should I return the original string's length, or is there a specific value I should return?
Can the input string be empty or null?
Are the substring removals performed iteratively until no further removals are possible, or is there a limit to the number of removal iterations?

Brute Force Solution

Approach

The brute force approach to finding the minimum string length after removing substrings involves repeatedly searching for specific substrings and removing them until no more removals are possible. We will explore all possible removal sequences to determine the shortest possible string. We essentially try every way to reduce the string until we can't anymore, then pick the shortest result.

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

Start with the original string.
Look for the target substrings in the string.
If a target substring is found, remove it.
After removing a substring, repeat the process of looking for and removing substrings from the new, shorter string.
Keep a record of the length of the string after each removal sequence.
Try removing the target substrings in a different order, repeating the removal process each time and recording the final string length.
Continue trying all possible orders of removal until all possibilities have been exhausted.
Compare the lengths of all the final strings obtained from different removal orders.
The shortest string found represents the minimum possible string length achievable, and that is our result.

Code Implementation

def minimum_string_length_after_removing_substrings(input_string):

    substrings_to_remove = ["AB", "CD"]
    minimum_length = len(input_string)

    def solve(current_string):
        nonlocal minimum_length
        minimum_length = min(minimum_length, len(current_string))

        can_remove = False
        for substring in substrings_to_remove:
            if substring in current_string:
                can_remove = True
                break
        
        # If we can't remove any substring, this branch is finished
        if not can_remove:
            return

        for substring in substrings_to_remove:
            index = current_string.find(substring)
            # Only try removing if the substring exists to avoid errors
            if index != -1:
                new_string = current_string[:index] + current_string[index+2:]

                # Explore the string after removing the substring
                solve(new_string)

    # Initiate the recursive exploration with the initial string
    solve(input_string)

    return minimum_length

Big(O) Analysis

Time Complexity

O(4^n) – The described brute force approach explores all possible removal sequences of substrings from the input string. In the worst-case scenario, each removal could potentially split the string into smaller pieces, requiring the algorithm to explore numerous combinations. The number of possible removal sequences grows exponentially with the input string length (n), as each position could potentially start a removal sequence for a target substring. Because there are potentially two substrings to remove, this effectively leads to a tree where each node has 2 children and a depth potentially equal to n/2 in the best case and close to n in the worst. The number of possible paths can thus be considered as O(2^(n/2) * 2^(n/2)) which is O(4^(n/2)) or O(4^n).

Space Complexity

O(N!) – The plain English explanation describes exploring all possible removal sequences of substrings. In the worst-case scenario, we might consider every possible order of removals. Each removal sequence leads to a new string derived from the input string, which could result in storing multiple intermediate strings. In the absolute worst-case scenario where 'N' substrings could be removed, the number of possible removal sequences can grow factorially (N!). Storing these intermediate results and tracking the sequences leads to a space complexity of O(N!).

Optimal Solution

Approach

The core idea is to repeatedly simplify the string by removing occurrences of the specified substrings. The optimal approach uses a stack to keep track of characters and efficiently identify and remove these substrings as they appear.

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

Think of a stack, which is like a pile where you can only add or remove things from the top.
Go through the input string character by character.
Put each character onto the top of the stack.
Every time you add a character, check if the characters on top of the stack form one of the substrings we want to remove (like 'AB' or 'CD').
If you find a substring, take those characters off the stack (effectively removing the substring).
If you don't find a substring, just keep going, adding more characters to the stack.
In the end, the characters left on the stack make up the shortest possible string after removing all the substrings we could find.

Code Implementation

def min_length_after_removal(input_string):
    stack = []

    for character in input_string:
        stack.append(character)

        # Check for 'AB' or 'CD' and remove if found.
        while len(stack) >= 2 and \
              ((stack[-2] == 'A' and stack[-1] == 'B') or \
               (stack[-2] == 'C' and stack[-1] == 'D')):

            # Removing the last two elements from the stack simulates substring removal.
            stack.pop()
            stack.pop()

    # The remaining characters in the stack form the minimized string.
    return len(stack)

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n once, pushing each character onto the stack. After each push, it checks if the top elements of the stack form a target substring ('AB' or 'CD'). The stack operations (push and pop) take constant time, O(1). The substring check also takes constant time since we're only comparing a fixed number of characters at the top of the stack. Thus, the time complexity is dominated by the single pass through the input string, resulting in O(n) time complexity.

Space Complexity

O(N) – The primary auxiliary space usage comes from the stack. In the worst-case scenario, none of the substrings can be removed, and the stack will contain all the characters from the input string. Therefore, the stack can grow up to a size of N, where N is the length of the input string. Thus, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Input string is null or empty	Return 0 immediately since no operations are possible.
Input string contains only 'AB' or 'CD' substrings repeatedly.	Repeated reductions are necessary until no more 'AB' or 'CD' exist.
Input string contains no 'AB' or 'CD' substrings.	Return the length of the original string as no reduction is possible.
Input string starts and ends with different characters.	This will likely result in a larger final string size compared to balanced inputs.
String length is at the maximum allowed size (e.g., 10^5).	Ensure the solution uses an efficient data structure (e.g., Stack) to avoid exceeding time limit.
Input String consists of only 'A', 'B', 'C', or 'D' characters, but contains no 'AB' or 'CD' pairs	The stack will simply accumulate the characters, and the final length will be equal to original length.
The string contains only 'A' and 'B' and removing many substrings	The solution must have the proper order check when pushing or popping from stack.
Memory constraints with very large input string.	Use in place modifications where possible or memory efficient string operations.

Input string is null or empty

How to Handle:

Return 0 immediately since no operations are possible.

Input string contains only 'AB' or 'CD' substrings repeatedly.

How to Handle:

Repeated reductions are necessary until no more 'AB' or 'CD' exist.

Input string contains no 'AB' or 'CD' substrings.

How to Handle:

Return the length of the original string as no reduction is possible.

Input string starts and ends with different characters.

How to Handle:

This will likely result in a larger final string size compared to balanced inputs.

String length is at the maximum allowed size (e.g., 10^5).

How to Handle:

Ensure the solution uses an efficient data structure (e.g., Stack) to avoid exceeding time limit.

Input String consists of only 'A', 'B', 'C', or 'D' characters, but contains no 'AB' or 'CD' pairs

How to Handle:

The stack will simply accumulate the characters, and the final length will be equal to original length.

The string contains only 'A' and 'B' and removing many substrings

How to Handle:

The solution must have the proper order check when pushing or popping from stack.

Memory constraints with very large input string.

How to Handle:

Use in place modifications where possible or memory efficient string operations.

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 possible substrings that can be removed, and are there any restrictions on the characters that can appear in the initial string?
What is the maximum length of the input string?
If no removals are possible, should I return the original string's length, or is there a specific value I should return?
Can the input string be empty or null?
Are the substring removals performed iteratively until no further removals are possible, or is there a limit to the number of removal iterations?

Brute Force Solution

Approach

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

Start with the original string.
Look for the target substrings in the string.
If a target substring is found, remove it.
After removing a substring, repeat the process of looking for and removing substrings from the new, shorter string.
Keep a record of the length of the string after each removal sequence.
Try removing the target substrings in a different order, repeating the removal process each time and recording the final string length.
Continue trying all possible orders of removal until all possibilities have been exhausted.
Compare the lengths of all the final strings obtained from different removal orders.
The shortest string found represents the minimum possible string length achievable, and that is our result.

Code Implementation

def minimum_string_length_after_removing_substrings(input_string):

    substrings_to_remove = ["AB", "CD"]
    minimum_length = len(input_string)

    def solve(current_string):
        nonlocal minimum_length
        minimum_length = min(minimum_length, len(current_string))

        can_remove = False
        for substring in substrings_to_remove:
            if substring in current_string:
                can_remove = True
                break
        
        # If we can't remove any substring, this branch is finished
        if not can_remove:
            return

        for substring in substrings_to_remove:
            index = current_string.find(substring)
            # Only try removing if the substring exists to avoid errors
            if index != -1:
                new_string = current_string[:index] + current_string[index+2:]

                # Explore the string after removing the substring
                solve(new_string)

    # Initiate the recursive exploration with the initial string
    solve(input_string)

    return minimum_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Think of a stack, which is like a pile where you can only add or remove things from the top.
Go through the input string character by character.
Put each character onto the top of the stack.
Every time you add a character, check if the characters on top of the stack form one of the substrings we want to remove (like 'AB' or 'CD').
If you find a substring, take those characters off the stack (effectively removing the substring).
If you don't find a substring, just keep going, adding more characters to the stack.
In the end, the characters left on the stack make up the shortest possible string after removing all the substrings we could find.

Code Implementation

def min_length_after_removal(input_string):
    stack = []

    for character in input_string:
        stack.append(character)

        # Check for 'AB' or 'CD' and remove if found.
        while len(stack) >= 2 and \
              ((stack[-2] == 'A' and stack[-1] == 'B') or \
               (stack[-2] == 'C' and stack[-1] == 'D')):

            # Removing the last two elements from the stack simulates substring removal.
            stack.pop()
            stack.pop()

    # The remaining characters in the stack form the minimized string.
    return len(stack)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input string is null or empty	Return 0 immediately since no operations are possible.
Input string contains only 'AB' or 'CD' substrings repeatedly.	Repeated reductions are necessary until no more 'AB' or 'CD' exist.
Input string contains no 'AB' or 'CD' substrings.	Return the length of the original string as no reduction is possible.
Input string starts and ends with different characters.	This will likely result in a larger final string size compared to balanced inputs.
String length is at the maximum allowed size (e.g., 10^5).	Ensure the solution uses an efficient data structure (e.g., Stack) to avoid exceeding time limit.
Input String consists of only 'A', 'B', 'C', or 'D' characters, but contains no 'AB' or 'CD' pairs	The stack will simply accumulate the characters, and the final length will be equal to original length.
The string contains only 'A' and 'B' and removing many substrings	The solution must have the proper order check when pushing or popping from stack.
Memory constraints with very large input string.	Use in place modifications where possible or memory efficient string operations.

Input string is null or empty

How to Handle:

Return 0 immediately since no operations are possible.

Input string contains only 'AB' or 'CD' substrings repeatedly.

How to Handle:

Repeated reductions are necessary until no more 'AB' or 'CD' exist.

Input string contains no 'AB' or 'CD' substrings.

How to Handle:

Return the length of the original string as no reduction is possible.

Input string starts and ends with different characters.

How to Handle:

This will likely result in a larger final string size compared to balanced inputs.

String length is at the maximum allowed size (e.g., 10^5).

How to Handle:

Ensure the solution uses an efficient data structure (e.g., Stack) to avoid exceeding time limit.

Input String consists of only 'A', 'B', 'C', or 'D' characters, but contains no 'AB' or 'CD' pairs

How to Handle:

The stack will simply accumulate the characters, and the final length will be equal to original length.

The string contains only 'A' and 'B' and removing many substrings

How to Handle:

The solution must have the proper order check when pushing or popping from stack.

Memory constraints with very large input string.

How to Handle:

Use in place modifications where possible or memory efficient string operations.

0/1114 Microsoft questions completed

0/1114 completed