We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum String Length After Removing Substrings

Difficulty: Easy

Problem Description

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.

Key Insights

  • Substrings "AB" and "CD" can be removed multiple times, potentially creating new opportunities for removal.
  • The problem can be approached using a stack-like structure to efficiently manage and reduce the string.
  • The operations are greedy; each time we encounter a removable substring, we should remove it immediately to minimize the length.

Space and Time Complexity

Time Complexity: O(n) - where n is the length of the input string, as we traverse the string once. Space Complexity: O(n) - in the worst case, we may need to store all characters in the stack.

Solution

To solve the problem, we can use a stack data structure to simulate the removal of substrings. As we iterate through the string, we push each character onto the stack. After pushing a character, we check the top two characters of the stack. If they form "AB" or "CD", we pop these two characters from the stack, effectively removing the substring from the current string. This process continues until we have processed all characters in the string. The final length of the stack will represent the minimum length of the string after all possible removals.

Code Solutions

def minimum_length(s: str) -> int:
    stack = []
    
    for char in s:
        stack.append(char)
        # Check if the last two characters form "AB" or "CD"
        if len(stack) >= 2 and ((stack[-1] == 'B' and stack[-2] == 'A') or (stack[-1] == 'D' and stack[-2] == 'C')):
            stack.pop()  # Remove last character
            stack.pop()  # Remove second last character
            
    return len(stack)
← Back to All Questions