Minimum Deletions to Make String Balanced (Easy Explanation)

If you’re doing your LeetCode daily streak and today you hit Question 1653 — “Minimum Deletions to Make String Balanced”, this one is all about turning a messy mix of a and b into a “clean” order with the fewest deletions.

Let’s break it down like a human would, not like a textbook.

What does “balanced” mean?

You’re given a string s containing only:

A string is balanced if all a characters come before any b characters.

So these are balanced ✅:

"aaaa"
"aaabbb"
"bbb" (yes — no a after b, so it’s fine)

These are NOT balanced ❌:

"ba" (because there’s a b before an a)
"aababbab" (because a appears after some b)

Another way to remember it:

A string is balanced if it has no "ba" pattern.

Goal

Delete the minimum number of characters (any positions you want) so the final string becomes balanced.

Quick examples

Example 1

Input: s = "aababbab"
Output: 2
You can delete 2 characters to make something like "aaabbb".

Example 2

Input: s = "bbaaaaabb"
Output: 2
Delete two b’s at the start (or some a’s in the middle), and it becomes balanced.

Key insight (the “aha” moment)

While scanning the string from left to right:

Every time you see a b, it’s fine — b can sit on the right side of a balanced string.
Every time you see an a after you’ve already seen some b’s, you have a conflict (a "ba" situation).

When that happens, you have only two logical choices:

Delete this a
→ cost: deletions + 1
Delete all previous b’s (so this a is no longer “after a b”)
→ cost: countB (number of b seen so far)

So at every problematic a, we choose the cheaper option:

deletions = min(deletions + 1, countB)

That’s the whole solution.

One-pass Greedy/DP Approach (Best for Interviews)

What we track

countB: how many b’s we’ve seen so far
deletions: minimum deletions needed up to the current position

Step-by-step logic

For each character:

If it’s 'b':
countB += 1
If it’s 'a':
deletions = min(deletions + 1, countB)

This works because we’re always keeping the best possible answer for the prefix we’ve processed.

Time and space complexity

Time: O(n) (single pass)
Space: O(1) (constant extra memory)

Perfect for large inputs.

Clean code solutions

✅ Python (LeetCode-ready)

class Solution:
    def minimumDeletions(self, s: str) -> int:
        countB = 0
        deletions = 0

        for ch in s:
            if ch == 'b':
                countB += 1
            else:  # ch == 'a'
                deletions = min(deletions + 1, countB)

        return deletions

✅ Java

class Solution {
    public int minimumDeletions(String s) {
        int countB = 0;
        int deletions = 0;

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == 'b') {
                countB++;
            } else { // 'a'
                deletions = Math.min(deletions + 1, countB);
            }
        }
        return deletions;
    }
}

✅ C++

class Solution {
public:
    int minimumDeletions(string s) {
        int countB = 0;
        int deletions = 0;

        for (char ch : s) {
            if (ch == 'b') {
                countB++;
            } else { // 'a'
                deletions = min(deletions + 1, countB);
            }
        }
        return deletions;
    }
};

Mini walkthrough (to make it stick)

Take: s = "ba"

Start: countB=0, deletions=0
See 'b' → countB=1
See 'a' → conflict:
- delete 'a' → deletions + 1 = 1
- delete previous 'b' → countB = 1
- choose min → deletions = 1

Answer: 1 ✅

Common mistakes people make

Thinking you need to “rebuild the string” — you don’t.
Using nested loops (goes O(n²) and can TLE).
Confusing the balanced condition (it’s all a before b, not the other way around).

FAQ

Is this dynamic programming or greedy?

It’s basically DP compressed into two variables. The update rule is DP-like, but it behaves greedily because we always choose the cheapest fix at each step.

Why is `"bbb"` balanced even with no `a`?

Because the rule is only: no a should appear after a b. If there are no a’s, nothing violates that.

Can I solve it with prefix/suffix counts?

Yes. You can compute:

prefix count of b
suffix count of a
and try every split. It’s still O(n) but uses extra arrays unless optimized.