DSA problem
Minimum Deletions to Make String Balanced
You are given a string s consisting only of the characters 'a' and 'b'. A string is balanced if there is no index i < j such that s[i] = 'b' and s[j] = 'a' — in other words, every 'b' appears after every 'a'. Return the minimum number of deletions needed to make s balanced.
The naive approach tries every split index k: count the 'b's in the prefix s[0..k-1] and the 'a's in the suffix s[k..], since those are the characters that violate the ordering. The minimum over all splits gives the answer in O(n) after computing prefix sums.
The slick one-pass formulation eliminates the prefix-sum arrays. Walk left to right while tracking two running quantities: bCount, the number of 'b's seen so far, and aDeletions, the minimum number of deletions needed to balance the prefix processed so far. When the next character is 'b', simply increment bCount. When it is 'a', we have a choice: delete this 'a' (aDeletions + 1) or delete every preceding 'b' (bCount). Either choice keeps the prefix balanced, and the greedy invariant maintains the optimal cost.
Although this problem is often solved with prefix counts, the running-minimum recurrence is equivalent to a monotonic stack of unmatched 'b's: each new 'a' is reconciled either by popping all earlier 'b's or by being deleted itself. The result is O(n) time and O(1) space.
Examples
s = "aababbab"2s = "bbaaaaabb"2s = "a"0Constraints
- 1 <= s.length <= 10^5
- s[i] is 'a' or 'b'.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.