Minimum Deletions to Make String Balanced Solution

Problem

You are given a string containing only the characters 'a' and 'b'. A string is balanced if no 'b' appears before any 'a' — in other words, all 'a's come before all 'b's. You can delete any character. Find the minimum number of deletions to make the string balanced.

Input: s = "aababbab"
Output: 2
Explanation: Deleting the two out-of-place 'b's (positions 2 and 4) yields "aaaabb", which is balanced.

Counter-example: "ba" requires 1 deletion — either remove the leading 'b' to get "a", or remove the trailing 'a' to get "b". Both single-character strings are trivially balanced.

Intuition

Imagine drawing an invisible dividing line somewhere in the string. Everything to the left of the line should be all 'a's, and everything to the right should be all 'b's. Any 'b' found left of the line and any 'a' found right of the line must be deleted. Sliding the line from left to right and taking the minimum total cost is the core idea.

The O(1)-space greedy insight is that when you encounter an 'a' after one or more 'b's, it is always at least as good to "eliminate" one of those earlier 'b's (cost 1) rather than accumulate more obligations for future characters.

Approach 1 — Prefix/Suffix Sweep

Precompute prefix 'b' counts and suffix 'a' counts, then try every possible split point and return the minimum total cost.

Build b_prefix[i] — the number of 'b's in s[0..i-1].
Build a_suffix[i] — the number of 'a's in s[i..n-1].
For each split index i from 0 to n, compute b_prefix[i] + a_suffix[i].
Return the minimum over all split indices.

1def min_deletions(s: str) -> int:
2    n = len(s)
3
4    # b_prefix[i] = number of 'b's strictly before index i
5    b_prefix = [0] * (n + 1)
6    for i in range(n):
7        b_prefix[i + 1] = b_prefix[i] + (1 if s[i] == 'b' else 0)
8
9    # a_suffix[i] = number of 'a's at index i or later
10    a_suffix = [0] * (n + 1)
11    for i in range(n - 1, -1, -1):
12        a_suffix[i] = a_suffix[i + 1] + (1 if s[i] == 'a' else 0)
13
14    # try every split: left side should be all 'a's, right side all 'b's
15    return min(b_prefix[i] + a_suffix[i] for i in range(n + 1))

Time: O(n) — two linear passes to build the arrays, one pass to find the minimum.

Space: O(n) — two auxiliary arrays of length n+1.

Approach 2 — Greedy Single Pass

Scan left to right, keeping a count of unresolved 'b's. When an 'a' is encountered after at least one 'b', one deletion is unavoidable — greedily "remove" one 'b' from the count (equivalent to choosing whichever deletion costs less at that moment).

Initialize b_count = 0 and deletions = 0.
For each character:
- If 'b': increment b_count (one more 'b' that could conflict with a future 'a').
- If 'a' and b_count > 0: increment deletions and decrement b_count — we logically removed one conflicting 'b', keeping the 'a' so it doesn't obstruct future 'b's.
Return deletions.

1def min_deletions(s: str) -> int:
2    b_count = 0    # unresolved 'b's seen so far
3    deletions = 0
4
5    for ch in s:
6        if ch == 'b':
7            b_count += 1
8        elif b_count > 0:
9            # deleting one 'b' is always at least as good as deleting this 'a'
10            b_count -= 1
11            deletions += 1
12
13    return deletions

Time: O(n) — a single pass through the string.

Space: O(1) — only two integer counters.

Complexity Summary

Approach	Time	Space	When to use
Prefix/Suffix Sweep	O(n)	O(n)	When you want the explicit split point or need to reconstruct the result
Greedy Single Pass	O(n)	O(1)	Default choice — cleanest and most space-efficient

Common Mistakes

Forgetting the boundary split points. The split can be at index 0 (all 'a's deleted, string is all 'b's) or index n (all 'b's deleted, string is all 'a's). Both endpoints must be included in the sweep.
Not decrementing b_count in the greedy. After handling a conflicting 'a', b_count must decrease by 1. Skipping this leaves the counter inflated, causing over-counting of deletions for future characters.
Deleting 'a's only. It is equally valid to delete a 'b' — the algorithm works because each conflict requires exactly one deletion regardless of which character is removed.
Confusing "balanced" with "sorted". A string of all 'b's ("bbb") is balanced; "ba" is not. Students sometimes assume balanced means mixed but ordered, and incorrectly penalise pure-'b' or pure-'a' strings.
Using the prefix sweep without O(n) space optimization awareness. Candidates who reach this in an interview often miss that the sweep can be reduced to O(1) space by computing a_suffix on the fly in reverse.

Minimum Deletions to Make String Balanced — Solution