Solution: Minimum String Length After Removing Substrings

Let’s solve the Minimum String Length After Removing Substrings problem using the Stacks pattern.

We'll cover the following

Statement

You are given a string, s, containing only uppercase English letters. You can perform operations on this string where, in each operation, you remove any occurrence of the substrings "AB" or "CD" from s.

Your task is to return the shortest string length after applying all possible operations.

Note: After each removal, the string joins back together, potentially creating new occurrences of "AB" or "CD" that can also be removed.

Constraints:

  • 1≤1 \leq s.length ≤100\leq 100

  • s consists only of uppercase English letters.

Solution

This algorithm uses a stack to iteratively remove all substrings "AB" and "CD" occurrences from the string. The idea is to use the stack to track characters and check if the current character forms an "AB” or "CD” pair with the top character in the stack. If a match is found, the pair is removed by popping the top element from the stack. Otherwise, the current character is added to the stack. This approach allows for efficient pairwise removal without needing additional string scans, ultimately leaving the stack with only the characters that couldn’t form any “AB” or “CD” pairs.

The algorithm steps are as follows:

  1. Create an empty stack to hold characters temporarily as we process the string.

  2. Iterate through the string and for each character current_char in the string:

    1. If the stack is empty, add current_char to the stack.

    2. Check for "AB" or "CD" pairs:

      1. If current_char is "B" and the top character in the stack is "A", it means we found an "AB" pair, so we remove this pair by popping the stack.

      2. If current_char is "D" and the top character in the stack is "C", it indicates a "CD" pair, so we remove this pair by popping the stack.

    3. If no pair is found, push the current character onto the stack.

  3. After processing all characters, the stack length represents the shortest possible length of the string after all removals.

Let’s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.