Leetcode Daily Question 07/10/2024 - 2696. Minimum String Length After Removing Substrings

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.

class Solution:
  def minLength(self, s: str) -> int:
    stack = []
        
    for char in s:
      if stack and ((stack[-1] == 'A' and char == 'B') or (stack[-1] == 'C' and char == 'D')):
        stack.pop()
          else:
            stack.append(char)
        
    return len(stack)

Explanation:

We can use a stack to eliminate the pairs continuously. This way, we avoid having to repeated remove substrings.

A stack is first in first out. So the last element you add into the stack is always the first to be removed.

So, when we have an "A" as our last item in the stack for example, and we encounter "B". We pop the "A" and do not add the "B". This is the same as removing "AB".

def minLength(s):
    stack = []
        
    for char in s:
      if stack and ((stack[-1] == 'A' and char == 'B') or (stack[-1] == 'C' and char == 'D')):
        stack.pop()
          else:
            stack.append(char)
        
    return len(stack)

The time complexity is O(n) as we only need to pass through the array once.

The space complexity is O(n) as we may not need to remove any substring hence len(stack) = len(s) = n.

The full solution can be found near the top of the page.