Minimum Deletions To Make String Balanced
01 · Problem
You are given a string s made only of the characters 'a' and 'b'. The string is balanced when no 'b' appears anywhere before an 'a', i.e. it looks like some 'a's followed by some 'b's (either group may be empty).
You may delete any characters you like. Return the minimum number of deletions needed to make s balanced. An already balanced string needs 0 deletions.
02 · Examples
s = "abba"
1
Deleting the final 'a' gives "abb", which is balanced. One deletion is unavoidable because a 'b' precedes that 'a'.
s = "babaab"
2
Deleting the 'b's at indices 0 and 2 leaves "aaab", which is balanced. One deletion is not enough.
s = "aabb"
0
All 'a's already come before all 'b's.
03 · Constraints
- 011 <= s.length <= 105
- 02s[i] is either 'a' or 'b'
- 03A deletion removes exactly one character
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.