💬 Discord
Sign In
NeetCode #367LC-2696EasyStack
← Back to All Problems

#367 · #2696 · Minimum String Length After Removing Substrings(删除子串后的字符串最小长度)

📌 Problem Statement & Constraints

Given a string s of uppercase letters, repeatedly remove any occurrence of "AB" or "CD" until no more exist. Return the minimum possible length. Constraints: 1 <= s.length <= 100.

💡 Core Algorithmic Approaches

  1. A stack removes the removable pairs in one pass.
  2. If the stack top plus the current character forms "AB" or "CD", pop; otherwise push.
  3. Removals can expose new pairs, but the stack handles this because the next character is compared against the new top.
  4. The answer is the stack size.

💻 Benchmark Python3 Implementation

class Solution:
    def minLength(self, s: str) -> int:
        st = []
        for ch in s:
            if st and ((st[-1] == "A" and ch == "B") or (st[-1] == "C" and ch == "D")):
                st.pop()                   # the pair cancels
            else:
                st.append(ch)
        return len(st)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each character is pushed or popped once.
💾 Space Complexity
O(n) for the stack.

⚠️ Interview Pitfalls & Follow-ups

  • Only checking "AB": "CD" is also removable.
  • Rescanning until stable: the stack already produces the fixpoint in one pass.
  • Confusing this with adjacent-duplicate removal: the pairs are different letters, not equal ones.
  • Assuming the removals are order-independent: the greedy stack is correct because any removable pair can be cancelled in any order and the final length is invariant.