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
• b

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:

1. Delete this a
   → cost: deletions + 1
2. 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.