Skip to main content
Talentd

Minimum String Length After Balanced Removals - Solution & Explanation

MediumStringStackCounting6 min read
Practice this problem

Problem Statement

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 <= 105
  • s[i] is either 'a' or 'b'.

Approach Overview

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.

Solution

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Stack SimulationO(n)O(n)Useful for visualizing the removal process or when practicing stack-based string reductions
Counting / Frequency AnalysisO(n)O(1)Optimal solution for interviews and large inputs since it avoids simulation

Video Solution

Leetcode Weekly Contest 476 Q2. Minimum String Length After Balanced Removals #python #dsa • ADevOpsEngineer • 175 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum String Length After Balanced Removals easy or hard?
The problem is typically classified as Medium because the optimal solution requires recognizing the frequency imbalance insight. A straightforward simulation is easy to implement, but deriving the counting formula requires deeper reasoning about how removals interact.
Minimum String Length After Balanced Removals Python/Java solution
Most implementations compute character frequencies using a dictionary or array, then apply the formula based on the maximum frequency and total length. The logic is identical across Python, Java, C++, Go, and TypeScript and runs in linear time.
How to solve Minimum String Length After Balanced Removals in O(n)?
Iterate through the string and count the frequency of each character. Let n be the string length and maxFreq be the highest frequency. If maxFreq > n - maxFreq, the remaining length is maxFreq - (n - maxFreq). Otherwise, the result is n % 2 because balanced removals cancel nearly all characters.
What is the best approach for Minimum String Length After Balanced Removals?
The most efficient solution uses frequency counting. Count how many times each character appears and track the maximum frequency. If the most frequent character exceeds the count of all other characters combined, some characters cannot be paired and remain. Otherwise, nearly all characters cancel out, leaving either 0 or 1 depending on whether the total length is even or odd. This runs in O(n) time and O(1) space.
Is Minimum String Length After Balanced Removals asked at Google/Amazon/Meta?
Problems based on greedy counting and string cancellation patterns frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving removing pairs, balancing characters, or minimizing remaining length are common interview exercises.
What data structure is used in Minimum String Length After Balanced Removals?
The optimal approach uses a frequency counter, typically implemented with a fixed-size array or hash map. A stack can also be used in a simulation approach to model pair removals during traversal, though it requires more memory.
What is the time complexity of Minimum String Length After Balanced Removals?
The optimal counting solution runs in O(n) time because it scans the string once to compute character frequencies. Space complexity is O(1) since the alphabet size is fixed and only a small frequency array or map is required.

Ready to solve this problem?

Practice Minimum String Length After Balanced Removals with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring