This problem requires calculating the minimum deletions to make a string balanced, meaning no 'b' appears before 'a'. Use a state transition dynamic programming approach to track deletions at each index efficiently. By counting preceding 'b's and remaining 'a's, you can decide at each step whether to delete the current character or retain it for optimal balance.
Problem Statement
Given a string s containing only 'a' and 'b', delete characters to ensure the string is balanced. A string is balanced if no 'b' occurs before an 'a'.
Return the minimum number of deletions required to achieve this balance. For example, given s = "aababbab", the minimum deletions needed are 2 to reorder it into a fully balanced string.
Examples
Example 1
Input: s = "aababbab"
Output: 2
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
The only solution is to delete the first two characters.
Constraints
- 1 <= s.length <= 105
- s[i] is 'a' or 'b'.
Solution Approach
Dynamic Programming State Transition
Track the minimum deletions needed at each index using a DP array. For each character, either delete it or account for previous 'b's to maintain balance.
Counting Preceding Bs and Following As
Maintain a running count of 'b's seen so far and 'a's remaining. At each index, the minimum deletions is either deleting the current 'b' or the remaining 'a's after it.
Optimized One-Pass Calculation
Use a single pass with two counters instead of full DP array to track deletions. Incrementally update minimum deletions by comparing current 'b' deletions versus future 'a' deletions.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(1) |
Time complexity is O(n) because we process each character once. Space complexity is O(1) using counters instead of full DP storage.
What Interviewers Usually Probe
- You may ask how to handle 'b's before 'a's efficiently using dynamic programming.
- They may hint at optimizing the DP array to constant space with counters.
- Expect discussion on trade-offs between deleting 'a's versus 'b's at each index.
Common Pitfalls or Variants
Common pitfalls
- Failing to count all 'a's after the current index leads to incorrect deletions.
- Trying a full DP array without realizing a simple counter can suffice.
- Misinterpreting balance conditions and deleting unnecessary characters.
Follow-up variants
- Compute minimum insertions instead of deletions to achieve balance.
- Handle strings with multiple character types and define custom order rules.
- Return the actual balanced string, not just the count of deletions.
How GhostInterview Helps
- Automatically applies the state transition DP pattern to find minimum deletions.
- Highlights failure modes like overcounting or miscounting 'a's and 'b's.
- Generates examples and explanations tailored to the exact string balancing challenge.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the core idea behind Minimum Deletions to Make String Balanced?
It involves deleting characters to ensure no 'b' occurs before an 'a', using a state transition dynamic programming approach.
Can this problem be solved in one pass?
Yes, by maintaining counters for preceding 'b's and remaining 'a's, you can compute minimum deletions in a single pass.
Why not delete all 'a's or all 'b's?
Deleting all of one character type is rarely optimal; the goal is minimal deletions using careful index tracking.
How does the DP state transition work here?
At each index, choose the smaller between deleting the current 'b' or deleting remaining 'a's to maintain balance.
Is extra space required for DP?
No, you can optimize to O(1) space with two counters instead of storing a full DP array.
Need direct help with Minimum Deletions to Make String Balanced instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Minimum Deletions to Make String Balanced from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Determine the minimum operations to change a boolean expression's result using state transition dynamic programming efficiently.
Open problem page#2019 The Score of Students Solving Math ExpressionCalculate student scores for a single-digit math expression using state transition dynamic programming to track all valid outcomes efficiently.
Open problem page#678 Valid Parenthesis StringSolve the Valid Parenthesis String problem by leveraging state transition dynamic programming to handle parentheses and wildcard '*' characters.
Open problem page