Minimum String Length After Removing Substrings

medium string stack simulation

Problem

You are given a string s of only the characters A, B, C and D. In one operation you may delete any occurrence of the substring "AB" or the substring "CD". After deleting, the string joins back together and may form new "AB" or "CD" pairs, which you can keep deleting. Return the minimum possible length of the string after any number of operations.

Inputs = "ABFCACDB"

Output2

"ABFCACDB" → remove AB → "FCACDB" → remove CD → "FCAB" → remove AB → "FC". Length 2.

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

function minLength(s) {
  const stack = [];
  for (const c of s) {
    const top = stack[stack.length - 1];
    if (stack.length && ((top === 'A' && c === 'B') ||
                         (top === 'C' && c === 'D'))) {
      stack.pop();
    } else {
      stack.push(c);
    }
  }
  return stack.length;
}

class Solution {
    public int minLength(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && ((stack.peek() == 'A' && c == 'B') ||
                                    (stack.peek() == 'C' && c == 'D'))) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return stack.size();
    }
}

int minLength(string s) {
    string stack = "";
    for (char c : s) {
        if (!stack.empty() && ((stack.back() == 'A' && c == 'B') ||
                              (stack.back() == 'C' && c == 'D'))) {
            stack.pop_back();
        } else {
            stack.push_back(c);
        }
    }
    return stack.size();
}

Explanation

Removing "AB" or "CD" can cascade: deleting a pair can bring two new neighbours together that themselves form a removable pair. Re-scanning the whole string after each deletion would be slow, so we use a stack to resolve every cascade in a single left-to-right pass.

The stack holds the characters that have survived so far. As we read each character c, we peek at the top of the stack. If the top together with c forms "AB" (top is 'A', c is 'B') or "CD" (top is 'C', c is 'D'), the pair annihilates: we pop the top and drop c entirely.

Otherwise c cannot cancel with anything yet, so we push it onto the stack. This naturally handles chained removals: after a pop, the new top might pair up with a future character.

When the scan finishes, whatever remains on the stack is the fully reduced string, and its size is the minimum possible length. The order of deletions never matters here, so this greedy stack pass always reaches the smallest result.

Example: "ABFCACDB". Pushing A then reading B pops it; F, C, A, C get pushed; reading D pops the top C; reading B pops the top A — the stack ends as [F, C], so the answer is 2.

Time: O(n) Space: O(n)