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 <= 40s consists of uppercase English letters.
Hints for Minimum String Length After Removing Substrings
Hint 1
The order of removals does not change the final length, so a single left-to-right pass suffices.
Hint 2
Push characters on a stack, but cancel when a
Blands on anA, or aDon aC.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
- For each
ch, pop if it completesABorCDwith the top; else push. - 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