Minimum String Length After Removing Substrings - Solution & Explanation
Problem Statement
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 <= 100sconsists only of uppercase English letters.
Approach Overview
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 1: Stack-Based Approach
This approach revolves around using a stack to efficiently identify and remove the substrings "AB" and "CD" from the given string. By traversing each character of the string:
- If the current character and the top of the stack form "AB" or "CD", pop from the stack as they form a pattern to remove.
- If not, push the current character onto the stack. This keeps future potential patterns intact until further examination.
The characters that remain on the stack are the ones that could not form any removable patterns, thus forming the result string.
This implementation carries out a linear traversal of the string and uses a simple array to simulate stack operations. The stack's top is managed using an integer (top) that tracks the index of the last element.
Complexity
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), to store the stack elements, based on the worst case where no pairs are removed.
Approach 2: Two-Pointer Iterative Method
This technique uses a two-pointer approach to reduce the string by altering it in place. The core idea is to selectively overwrite positions in the string:
- Incrementally check pairs of characters: if they comprise a known removable substring, skip them both.
- If not, replace the write pointer's position with the read character, then advance the write position after adjustments.
After reaching the end of the string, the length of the string from the start to the write pointer represents the reduced string length.
This method involves editing the string in place. With two pointers ('read' and 'write'), we adjust the string as we progress. The write pointer helps track the new end of the string by overwriting unnecessary characters.
Complexity
Time Complexity: O(n), dependent on examining each character once.
Space Complexity: O(1), as no additional data structures are used.
Approach 3: Stack
We traverse the string s. For the current character c we are traversing, if the stack is not empty and the top element of the stack top can form AB or CD with c, then we pop the top element of the stack, otherwise we push c into the stack.
The number of remaining elements in the stack is the length of the final string.
In implementation, we can pre-place an empty character in the stack, so there is no need to judge whether the stack is empty when traversing the string. Finally, we can return the size of the stack minus one.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the string s.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Rust
Approach 4: One-liner
Code
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Stack-Based Approach | Time Complexity: O(n), where n is the length of the string. |
| Two-Pointer Iterative Method | Time Complexity: O(n), dependent on examining each character once. |
| Stack | — |
| One-liner | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Minimum String Length After Removing Substrings - Leetcode 2696 - Python • NeetCodeIO • 7,148 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum String Length After Removing Substrings easy or hard?
Minimum String Length After Removing Substrings Python/Java solution
How to solve Minimum String Length After Removing Substrings in O(n)?
What is the best approach for Minimum String Length After Removing Substrings?
Is Minimum String Length After Removing Substrings asked at Google/Amazon/Meta?
What data structure is used in Minimum String Length After Removing Substrings?
What is the time complexity of Minimum String Length After Removing Substrings?
Ready to solve this problem?
Practice Minimum String Length After Removing Substrings with our built-in code editor and test cases.
Practice on FleetCode