Problem of The Day: Minimum String Length After Removing Substrings

Problem Statement

Intuition

The problem requires reducing a string by removing specific character pairs (‘AB’ and ‘CD’) until no such pairs remain. The goal is to determine the minimum length of the string after all possible reductions. Initially, the thought process involves iteratively removing these pairs from the string until it no longer contains them.

Approach

1. Start with the given string and repeatedly apply the replacements.
2. In each iteration:
   • Replace all instances of ‘AB’ with an empty string ('').
   • Replace all instances of ‘CD’ with an empty string ('').
3. Continue these replacements until no more ‘AB’ or ‘CD’ pairs are found in the string.
4. After all possible reductions are made, return the length of the resulting string.

This approach ensures that all instances of the specified pairs are removed, and we are left with the shortest possible version of the string.

Complexity

• Time complexity:
  • \(O(n^2)\) in the worst case, where (n) is the length of the string. Each replacement can take up to (O(n)), and in the worst case, we might perform up to (O(n)) replacements.
• Space complexity:
  • \(O(1)\), if we consider the space required for the input string as part of the input. Only a constant amount of extra space is used for the replacements.

Code

class Solution:
    def minLength(self, s: str) -> int:
        while True:
            s = s.replace('AB', '')
            s = s.replace('CD', '')
            if 'AB' not in s and 'CD' not in s:
                break
        return len(s)

Editorial

Approach 1: String Replace

class Solution:
    def minLength(self, s: str) -> int:
        # Continue processing while "AB" or "CD" substrings exist
        while "AB" in s or "CD" in s:
            if "AB" in s:
                # Remove all occurrences of "AB"
                s = s.replace("AB", "")
            elif "CD" in s:
                # Remove all occurrences of "CD"
                s = s.replace("CD", "")

        return len(s)

• time: O(n^2)
• space: O(n)

Approach 2: Stack

class Solution:
    def minLength(self, s: str) -> int:
        stack = []

        # Iterate over each character in the input string
        for current_char in s:
            # If the stack is empty, simply push the current character
            if not stack:
                stack.append(current_char)
                continue

            # Check for "AB" pattern, remove the pair by popping from the stack
            if current_char == "B" and stack[-1] == "A":
                stack.pop()
            # Check for "CD" pattern, remove the pair by popping from the stack
            elif current_char == "D" and stack[-1] == "C":
                stack.pop()
            # Otherwise, push the current character onto the stack
            else:
                stack.append(current_char)

        return len(stack)

• time: O(n)
• space: O(n)