Watch 10 video solutions for Minimum Deletions to Make String Balanced, a medium level problem involving String, Dynamic Programming, Stack. This walkthrough by codestorywithMIK has 19,235 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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'.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 | 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. |