You are given a string s consisting only of the characters 'a' and 'b'.
You are allowed to repeatedly remove any substring where the number of 'a' characters is equal to the number of 'b' characters. After each removal, the remaining parts of the string are concatenated together without gaps.
Return an integer denoting the minimum possible length of the string after performing any number of such operations.
Example 1:
Input: s = "aabbab"
Output: 0
Explanation:
The substring "aabbab" has three 'a' and three 'b'. Since their counts are equal, we can remove the entire string directly. The minimum length is 0.
Example 2:
Input: s = "aaaa"
Output: 4
Explanation:
Every substring of "aaaa" contains only 'a' characters. No substring can be removed as a result, so the minimum length remains 4.
Example 3:
Input: s = "aaabb"
Output: 1
Explanation:
First, remove the substring "ab", leaving "aab". Next, remove the new substring "ab", leaving "a". No further removals are possible, so the minimum length is 1.
Constraints:
1 <= s.length <= 105s[i] is either 'a' or 'b'.Problem Overview: You are given a string and can repeatedly remove a balanced pair of characters where the two removed characters are different. The goal is to determine the minimum possible length of the string after performing these removals optimally.
Approach 1: Stack Simulation (O(n) time, O(n) space)
A direct way to simulate the process is to iterate through the string while maintaining a stack. For each character, check the top of the stack. If the top character is different, you can remove this balanced pair by popping the stack instead of pushing the new character. Otherwise, push the current character onto the stack. This approach mimics repeatedly removing valid pairs during traversal. It works well for understanding the mechanics of the problem but uses additional memory proportional to the string length.
Approach 2: Counting Frequencies (O(n) time, O(1) space)
The key insight is that each operation removes two different characters. Instead of simulating removals, count how many times each character appears. Let n be the total length and maxFreq be the highest frequency of any character. If the most frequent character appears more times than all other characters combined, some of it cannot be paired with different characters. The remaining length becomes maxFreq - (n - maxFreq). Otherwise, characters can cancel each other out almost completely, leaving either 0 or 1 depending on whether n is even or odd. This transforms the problem into a simple counting calculation.
This approach relies purely on frequency analysis using concepts from string processing and counting. The simulation alternative demonstrates how removals behave using a stack, but the counting method avoids unnecessary operations and achieves constant extra space.
Recommended for interviews: The counting approach is what interviewers typically expect. Explaining the stack simulation first shows you understand the removal process. Then derive the frequency-based formula to reduce the problem to O(n) time and O(1) space, which demonstrates stronger algorithmic insight.
According to the problem description, as long as adjacent characters are different, we can remove them. Therefore, the final remaining string will only contain the same character, either all 'a' or all 'b'. So we only need to count the number of 'a' and 'b' in the string, and the final minimum length is the absolute difference between their counts.
The time complexity is O(n), where n is the length of the string. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack Simulation | O(n) | O(n) | Useful for visualizing the removal process or when practicing stack-based string reductions |
| Counting / Frequency Analysis | O(n) | O(1) | Optimal solution for interviews and large inputs since it avoids simulation |
Leetcode Weekly Contest 476 Q2. Minimum String Length After Balanced Removals #python #dsa • ADevOpsBeginner • 174 views views
Watch 9 more video solutions →Practice Minimum String Length After Balanced Removals with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor