Watch 10 video solutions for Minimum String Length After Removing Substrings, a easy level problem involving String, Stack, Simulation. This walkthrough by NeetCodeIO has 6,981 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string s consisting only of uppercase English letters.
You can apply some operations to this string where, in one operation, you can remove any occurrence of one of the substrings "AB" or "CD" from s.
Return the minimum possible length of the resulting string that you can obtain.
Note that the string concatenates after removing the substring and could produce new "AB" or "CD" substrings.
Example 1:
Input: s = "ABFCACDB" Output: 2 Explanation: We can do the following operations: - Remove the substring "ABFCACDB", so s = "FCACDB". - Remove the substring "FCACDB", so s = "FCAB". - Remove the substring "FCAB", so s = "FC". So the resulting length of the string is 2. It can be shown that it is the minimum length that we can obtain.
Example 2:
Input: s = "ACBBD" Output: 5 Explanation: We cannot do any operations on the string so the length remains the same.
Constraints:
1 <= s.length <= 100s consists only of uppercase English letters.Problem Overview: You receive a string containing uppercase letters. You can repeatedly remove the substrings "AB" and "CD". Each removal shortens the string and may create new removable pairs. The goal is to return the minimum possible length after no more valid substrings remain.
Approach 1: Stack-Based Simulation (O(n) time, O(n) space)
This approach treats the problem as a streaming removal process using a stack. Iterate through the string character by character. For each character, check the top of the stack. If the top forms "AB" or "CD" with the current character, pop the stack instead of pushing the new character. This simulates removing the substring immediately. Otherwise, push the current character onto the stack.
The key insight: every valid removal only depends on the most recent character that remains in the string. A stack naturally models this behavior. Each character is pushed and popped at most once, giving O(n) time complexity with O(n) auxiliary space. This approach is straightforward and mirrors the exact removal process described in the problem.
Approach 2: Two-Pointer Iterative Method (O(n) time, O(1) extra space)
You can simulate the same behavior using a write pointer instead of an explicit stack. Convert the string into a mutable array and maintain a pointer that represents the current "stack top". Iterate through the characters with a second pointer. If the current character together with the previous written character forms "AB" or "CD", move the write pointer back (effectively deleting the pair). Otherwise, write the character and move the pointer forward.
This technique behaves like a stack but stores results directly inside the original array. Because the algorithm only moves pointers and overwrites characters, the extra memory usage drops to O(1). Time complexity remains O(n) since each character is processed once. This is a common pattern in two pointer and simulation problems where the result can be built in-place.
Recommended for interviews: The stack-based approach is the most intuitive and is typically what interviewers expect first. It clearly demonstrates how you model repeated removals using a data structure. The two-pointer variant shows deeper optimization skills by eliminating the extra stack and performing the same logic in-place while maintaining O(n) time.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Simulation | O(n) | O(n) | Most intuitive solution; clearly models substring removals and is easy to implement during interviews |
| Two-Pointer Iterative Method | O(n) | O(1) | Preferred when minimizing memory usage or when modifying the string in-place |