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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum String Length After Removing Substrings

Number: 2800

Difficulty: Easy

Paid? No

Companies: IBM, Amazon, Yelp, J.P. Morgan

Problem Description

Given a string s consisting only of uppercase English letters, you can repeatedly remove any occurrence of the substrings "AB" or "CD". Removing a substring causes the remaining parts of the string to concatenate, possibly creating new subsequences eligible for removal. The task is to determine the minimum possible length of s after applying these operations as many times as possible.

Key Insights

  • A stack provides an effective way to simulate the removal process.
  • As you iterate through s, compare the current character with the top of the stack.
  • When the two characters form either "AB" or "CD", pop the stack (simulate removal).
  • The remaining characters in the stack represent the minimized string length.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(n) in the worst-case scenario.

Solution

We employ a stack to process the string from left to right. For each character, we check if it, together with the top element of the stack, forms a removable substring ("AB" or "CD"). When it does, we pop the top element, effectively removing the pair. Otherwise, we push the current character onto the stack. After iterating through the entire string, the size of the stack indicates the minimum achievable length.

Code Solutions

# Python solution using a stack.
def min_length_after_removals(s):
    stack = []  # Initialize an empty stack.
    for char in s:
        # If the stack is not empty and the top element with the current character form a removable pair:
        if stack and ((stack[-1] == 'A' and char == 'B') or (stack[-1] == 'C' and char == 'D')):
            stack.pop()  # Remove the pair.
        else:
            stack.append(char)  # Otherwise, push the current character onto the stack.
    return len(stack)  # The final length is the size of the stack.

# Example usage
if __name__ == '__main__':
    print(min_length_after_removals("ABFCACDB"))  # Expected output: 2
    print(min_length_after_removals("ACBBD"))     # Expected output: 5
← Back to All Questions