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'.The goal of #1653 Minimum Deletions to Make String Balanced is to ensure that no 'b' appears before an 'a'. In other words, the final string should have all 'a' characters before any 'b'. A key observation is that every imbalance happens when a 'b' appears before a later 'a', forcing a deletion decision.
An efficient strategy uses a greedy or dynamic programming perspective. As you scan the string from left to right, track how many 'b' characters have been seen. When encountering an 'a' after some 'b's, you must decide whether to delete this 'a' or delete previous 'b's. Maintaining the minimum deletions so far leads to an optimal result.
This idea can also be implemented with a stack-like or counter-based approach that incrementally fixes violations. The process only requires a single pass through the string, giving O(n) time complexity and O(1) extra space for the optimized approach.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy / Counter Tracking | O(n) | O(1) |
| Dynamic Programming | O(n) | O(n) or O(1) optimized |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
You need to find for every index the number of Bs before it and the number of A's after it
You can speed up the finding of A's and B's in suffix and prefix using preprocessing
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.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), since we're using constant space.
1#include <stdio.h>
2#include <string.h>
3
4int minDeletionsToMakeBalanced(char* s) {
5 int n = strlen(s
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this type of string optimization problem appears in technical interviews at large companies. It tests understanding of greedy thinking, dynamic programming transitions, and the ability to reason about prefix decisions.
A simple counter-based technique works best, though the idea can be visualized with a stack. In practice, maintaining counts of previous 'b' characters and current deletions is enough to compute the minimum efficiently.
The optimal approach scans the string once while tracking how many 'b' characters have appeared so far. When an 'a' appears after those 'b's, you decide whether to delete that 'a' or remove previous 'b's. This greedy or DP-based strategy achieves O(n) time with O(1) extra space.
Yes. While it can be formulated as a DP problem, a greedy one-pass solution using counters achieves the same optimal result. This optimized approach reduces space usage while keeping the time complexity linear.