Minimum String Length After Removing Substrings

remove ab and cd and return minimum length remaining

Minimum String Length After Removing Substrings

Problem

You are given a string s made of only uppercase English letters.

In one operation, you can remove any occurrence of the substring "AB" or "CD" from s.

Return the minimum possible length of the string after all possible removals.

After a removal, the string joins together. This can create new "AB" or "CD" substrings.

Examples

Example 1

Input: s = "ABFCACDB"
Output: 2

• Remove "AB" from the start, so the string becomes "FCACDB".
• Remove "CD", so the string becomes "FCAB".
• Remove "AB", so the string becomes "FC".
• No more removals are possible. The length is 2.

Example 2

Input: s = "ACBBD"
Output: 5

• The string has no "AB" and no "CD".
• We cannot do any operation, so the length stays 5.

Constraints

• 1 <= s.length <= 100
• s has only uppercase English letters.

Main Idea

When we remove a pair, the letters on its left and right become new neighbors. They can form a new "AB" or "CD". So we always need the last kept letter. This is a job for a stack.

We read the string from left to right. For each letter:

• Letter is B and the top is A: We found "AB". Pop the top. Both letters are removed.
• Letter is D and the top is C: We found "CD". Pop the top. Both letters are removed.
• Anything else: Push the letter.

At the end, the stack holds all the letters that could not be removed. So the size of the stack is the answer.

Note: We only compare with the top. The top is always the last letter still in the string. So it is the same as checking the left neighbor of the current letter.

Stack Class Used in the Solution

The solution uses peek() and size(). Here is the Stack class with a size method added.

class Stack {
    constructor() {
        this.items = [];
    }

    push(element) {
        this.items.push(element);
    }

    pop() {
        if (this.isEmpty()) return "Stack Underflow";
        return this.items.pop();
    }

    // returns null when the stack is empty
    peek() {
        return this.isEmpty() ? null : this.items[this.items.length - 1];
    }

    isEmpty() {
        return this.items.length === 0;
    }

    // number of elements in the stack
    size() {
        return this.items.length;
    }
}

Solution: Stack

var minLength = function (str) {
    let stack = new Stack();

    for (let s of str) {
        if (s === 'B' && stack.peek() == 'A') {
            // found "AB", so remove the pair
            stack.pop();
        } else if (s === 'D' && stack.peek() === 'C') {
            // found "CD", so remove the pair
            stack.pop();
        } else {
            // no pair, so keep the letter
            stack.push(s);
        }
    }

    // the letters left in the stack are the final string
    return stack.size();
};

How the Code Works

Step 1: Create the stack

• stack keeps the letters that are still in the string.

Step 2: Read each letter

• If the letter is B and the top is A, we pop. The pair "AB" is gone.
• If the letter is D and the top is C, we pop. The pair "CD" is gone.
• Otherwise, we push the letter.
• When the stack is empty, peek() gives null. A null is never equal to 'A' or 'C', so the letter is pushed. We never pop from an empty stack.

Step 3: Return the size

• Each letter left in the stack could not be removed.
• So stack.size() is the minimum length.

Why the order matters

• B removes only an A right before it, and D removes only a C right before it.
• For example, in "ACBBD", the B sees C on top, not A. So it cannot remove anything.
• Also, "BA" and "DC" are not removed, because only "AB" and "CD" are allowed.

Dry Run

Let us take s = "ABFCACDB".

The stack is [F, C], so the answer is 2.

Look at the last row. The A and B were not next to each other in the original string. They became neighbors only after "CD" was removed. The stack handled this without any extra work.

Complexity

• Time Complexity: O(n)
  • n is the length of the string.
  • Each letter is pushed at most once and popped at most once.
  • peek(), push(), pop() and size() take O(1) time.
• Space Complexity: O(n)
  • In the worst case, no pair is removed, so the stack holds all n letters.

Shorter Version (Optional)

We can use a plain array as the stack. Then stack.length gives the size.

var minLength = function (s) {
    let stack = [];

    for (let ch of s) {
        let top = stack[stack.length - 1];

        if ((ch === 'B' && top === 'A') || (ch === 'D' && top === 'C')) {
            // found "AB" or "CD", so remove the pair
            stack.pop();
        } else {
            // no pair, so keep the letter
            stack.push(ch);
        }
    }

    return stack.length;
};

• When the stack is empty, top is undefined. It never equals 'A' or 'C', so the letter is pushed.

Complexity

• Time Complexity: O(n), because each letter is pushed and popped at most once.
• Space Complexity: O(n), because the stack can hold all letters.

Comparison

Summary

• When a pair is removed, the letters around it can form a new pair. So we need the last kept letter.
• A stack gives us that letter at the top in O(1) time.
• If the current letter is B and the top is A, or the current letter is D and the top is C, pop. Otherwise, push.
• The size of the stack at the end is the minimum length.
• This problem is very close to Remove All Adjacent Duplicates In String. The only change is the pair rule: here the pairs are "AB" and "CD", not two equal letters.
• The solution runs in O(n) time and uses O(n) space.