Minimum Deletions to Make String Balanced - Solution & Explanation
Problem Statement
You are given a string s consisting only of characters 'a' and 'b'āāāā.
You can delete any number of characters in s to make s balanced. s is balanced if there is no pair of indices (i,j) such that i < j and s[i] = 'b' and s[j]= 'a'.
Return the minimum number of deletions needed to make s balanced.
Example 1:
Input: s = "aababbab"
Output: 2
Explanation: You can either:
Delete the characters at 0-indexed positions 2 and 6 ("aababbab" -> "aaabbb"), or
Delete the characters at 0-indexed positions 3 and 6 ("aababbab" -> "aabbbb").
Example 2:
Input: s = "bbaaaaabb" Output: 2 Explanation: The only solution is to delete the first two characters.
Constraints:
1 <= s.length <= 105s[i]is'a'or'b'āā.
Approach Overview
Problem Overview: You are given a string containing only 'a' and 'b'. The string is balanced if no 'b' appears before an 'a' (no "ba" pattern). The task is to delete the minimum number of characters so the remaining string becomes balanced.
Approach 1: Split Point Enumeration (Brute Force) (Time: O(n^2), Space: O(1))
A balanced string effectively looks like a block of 'a' characters followed by a block of 'b' characters. Try every possible split index i in the string. For the left side, count how many 'b' characters must be deleted to keep only 'a'. For the right side, count how many 'a' characters must be deleted to keep only 'b'. The minimum deletions across all split points gives the answer. This approach demonstrates the key observation about the structure of a balanced string but recalculates counts repeatedly, leading to quadratic time.
Approach 2: Prefix Count and Dynamic Adjustment (Time: O(n), Space: O(1))
Traverse the string once while tracking two values: the number of 'b' characters seen so far and the minimum deletions needed to keep the prefix balanced. When you encounter 'a', you have two choices: delete this 'a' (cost deletions + 1) or delete all previous 'b' characters (cost bCount). Take the minimum. When you encounter 'b', simply increase bCount. This dynamic adjustment effectively simulates the optimal split point while scanning, making it a clean linear-time solution. The technique is closely related to prefix reasoning often used in string problems and lightweight dynamic programming.
Approach 3: Stack-Based Simulation (Time: O(n), Space: O(n))
You can also model the constraint using a stack. Iterate through the string and push 'b' characters onto the stack. When an 'a' appears after a 'b', the pair forms a violation ("ba"). You can either delete the current 'a' or remove a previous 'b' from the stack. By greedily resolving these conflicts while counting deletions, the algorithm maintains a valid order. This approach is conceptually intuitive for developers comfortable with stack patterns, though it uses extra memory compared to the prefix method.
Recommended for interviews: The prefix count and dynamic adjustment approach is the expected solution. It runs in O(n) time with O(1) space and clearly demonstrates the core insight: at every 'a', decide whether deleting the current character or all previous 'b' characters is cheaper. Starting with the brute-force split explanation helps communicate the reasoning before optimizing.
Approach 1: Prefix Count and Dynamic Adjustment
This approach involves using prefix sums to count the number of 'b's seen until each index and adjusting to track the potential number of deletions to ensure a balanced string.
This C solution iterates through the string once to count total 'b's. Then it iteratively calculates the minimum deletions needed by adjusting counts of 'a' seen and remaining 'b's using a greedy approach.
Complexity
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), since we're using constant space.
Approach 2: Dynamic Programming
We define f[i] as the minimum number of characters to be deleted in the first i characters to make the string balanced. Initially, f[0]=0. The answer is f[n].
We traverse the string s, maintaining a variable b, which represents the number of character 'b' in the characters before the current position.
- If the current character is 'b', it does not affect the balance of the first
icharacters, sof[i]=f[i-1], then we updateb \leftarrow b+1. - If the current character is 'a', we can choose to delete the current character, so
f[i]=f[i-1]+1; or we can choose to delete the previous character 'b', sof[i]=b. Therefore, we take the minimum of the two, that is,f[i]=min(f[i-1]+1,b).
In summary, we can get the state transition equation:
$
f[i]=\begin{cases}
f[i-1], & s[i-1]='b'\
min(f[i-1]+1,b), & s[i-1]='a'
\end{cases}
The final answer is f[n].
We notice that the state transition equation is only related to the previous state and the variable b, so we can just use an answer variable ans to maintain the current f[i], and there is no need to allocate an array f.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1)$.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Approach 3: Enumeration + Prefix Sum
We can enumerate each position i in the string s, dividing the string s into two parts, namely s[0,..,i-1] and s[i+1,..n-1]. To make the string balanced, the number of characters we need to delete at the current position i is the number of character 'b' in s[0,..,i-1] plus the number of character 'a' in s[i+1,..n-1].
Therefore, we maintain two variables lb and ra to represent the number of character 'b' in s[0,..,i-1] and the number of character 'a' in s[i+1,..n-1] respectively. The number of characters we need to delete is lb+ra. During the enumeration process, we update the variables lb and ra.
The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the string s.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Prefix Count and Dynamic Adjustment | Time Complexity: O(n), where n is the length of the string. |
| Dynamic Programming | ā |
| Enumeration + Prefix Sum | ā |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Split Point Enumeration (Brute Force) | O(n^2) | O(1) | Good for understanding the structure of a balanced string and explaining the idea in interviews before optimization. |
| Prefix Count and Dynamic Adjustment | O(n) | O(1) | Optimal solution. Best for interviews and large inputs since it scans the string once. |
| Stack-Based Simulation | O(n) | O(n) | Useful when modeling ordering constraints with stack patterns or teaching the concept visually. |
Video Solution
Minimum Deletions to Make String Balanced | Multiple Approaches | Leetcode 1653 | codestorywithMIK ā¢ codestorywithMIK ā¢ 19,903 views views
Watch 9 more video solutions āFrequently Asked Questions
Is Minimum Deletions to Make String Balanced easy or hard?
Minimum Deletions to Make String Balanced Python/Java solution
How to solve Minimum Deletions to Make String Balanced in O(n)?
What is the best approach for Minimum Deletions to Make String Balanced?
Is Minimum Deletions to Make String Balanced asked at Google/Amazon/Meta?
What data structure is used in Minimum Deletions to Make String Balanced?
What is the time complexity of Minimum Deletions to Make String Balanced?
Ready to solve this problem?
Practice Minimum Deletions to Make String Balanced with our built-in code editor and test cases.
Practice on FleetCode