Minimum String Length After Removing Substrings

Easy
395.

Minimum String Length After Removing Substrings

Minimum String Length After Removing Substrings is an easy coding problem on strings, simulation and stack, asked in Amazon and Adobe interviews.

You are given a string s of uppercase letters. In one operation you may remove any occurrence of the substring "AB" or "CD".

Removing one may create a new one. Return the minimum possible length of the string after any number of operations.

Example 1

Input
s = "ABFCACDB"
Output
2
Explanation
Repeated removals leave "FC".

Example 2

Input
s = "ACBBD"
Output
5
Explanation
Nothing can be removed.

Example 3

Input
s = "ABCD"
Output
0

Constraints

  • 1 <= s.length <= 40
  • s consists of uppercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var minLength = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum String Length After Removing Substrings — Solution

Minimum String Length After Removing Substrings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum String Length After Removing Substrings is an easy coding problem on strings, simulation and stack, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Strings, Simulation, Stack
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a string s of uppercase letters. In one operation you may remove any occurrence of the substring "AB" or "CD".

Removing one may create a new one. Return the minimum possible length of the string after any number of operations.

Example 1

Input: s = "ABFCACDB"
Output: 2
Explanation: Repeated removals leave "FC".

Example 2

Input: s = "ACBBD"
Output: 5
Explanation: Nothing can be removed.

Example 3

Input: s = "ABCD"
Output: 0

Constraints

  • 1 <= s.length <= 40
  • s consists of uppercase English letters.

Hints for Minimum String Length After Removing Substrings

  1. Hint 1

    The order of removals does not change the final length, so a single left-to-right pass suffices.

  2. Hint 2

    Push characters on a stack, but cancel when a B lands on an A, or a D on a C.

  3. Hint 3

    Cancelling exposes the character underneath, letting chains collapse naturally.

How to solve Minimum String Length After Removing Substrings

Push characters on a stack, cancelling B on A and D on C; the final stack size is the answer.

Approach

  1. For each ch, pop if it completes AB or CD with the top; else push.
  2. Return the stack length.

Why it works

Removal order does not affect the final length, and the stack always removes a pair as soon as it forms, exposing any new pair underneath.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Other letters simply stay on the stack and block matches across them.

Reference solution

Python

def minLength(s: str) -> int:
    stack = []
    for ch in s:
        if stack and ((ch == "B" and stack[-1] == "A") or (ch == "D" and stack[-1] == "C")):
            stack.pop()
        else:
            stack.append(ch)
    return len(stack)

Java

public static int minLength(String s) {
    StringBuilder stack = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        char top = stack.length() > 0 ? stack.charAt(stack.length() - 1) : ' ';
        if ((c == 'B' && top == 'A') || (c == 'D' && top == 'C')) stack.deleteCharAt(stack.length() - 1);
        else stack.append(c);
    }
    return stack.length();
}

C++

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

JavaScript

var minLength = function(s) {
    const stack = [];
    for (let i = 0; i < s.length; i++) {
        const c = s.charAt(i);
        const top = stack.length > 0 ? stack[stack.length - 1] : "";
        if ((c === "B" && top === "A") || (c === "D" && top === "C")) stack.pop();
        else stack.push(c);
    }
    return stack.length;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Stack Data Structure