Minimum Deletions to Make String Balanced

Maintain the cheapest valid prefix

A balanced result has a split: every retained a is before every retained b. Scan left to right. Let bCount be the number of b characters seen, and let deletions be the minimum deletions needed to make the processed prefix balanced. When seeing b, increment bCount; keeping it never breaks a prefix. When seeing a, either delete this a and keep the current state, or delete every earlier b so this a can remain before future b values. Therefore set deletions = min(deletions + 1, bCount).

Defend the recurrence

At each a, those two choices exhaust the ways to restore the single-split property for the prefix. No detailed position DP is needed because bCount summarizes the cost of removing all conflicting b values. A prefix/suffix alternative precomputes b counts on the left and a counts on the right for every split, but costs extra space. The one-pass method is O(n) time and O(1) space. Test an already balanced string, all one character, alternating characters, and a leading b followed by a.