Minimum Deletions to Make String Balanced
Understanding the Problem
We need to find the minimum number of deletions so that the remaining string has all 'a's on the left and all 'b's on the right. There can be zero 'a's or zero 'b's in the final string, both are valid.
In a balanced string, there is some "split point" where everything to the left is 'a' and everything to the right is 'b'. That split point can sit at the very beginning (all 'b's), the very end (all 'a's), or anywhere in between. For a given split point, we delete all the 'b's on the left side and all the 'a's on the right side.
We want the split point that minimizes total deletions. Counting violations at each split leads to a prefix/suffix approach, and a single running count collapses it to one pass.
Key Constraints:
1 <= s.length <= 10^5--> With n up to 100,000, we need O(n log n) or better. O(n^2) would be 10 billion operations, far too slow.s[i]is'a'or'b'--> Only two characters. This simplifies the problem significantly since we only need to track counts of two values.
Approach 1: Try All Split Points (Brute Force)
Intuition
Enumerate every possible split point. A balanced string has the form aaa...bbb..., so there is some position k (from 0 to n) where everything before k should be 'a' and everything from k onward should be 'b'.
For each split point k, count how many 'b's appear in the left portion (indices 0 to k-1) and how many 'a's appear in the right portion (indices k to n-1). The sum of these two counts is the number of deletions needed for that split. We try all n+1 possible splits and return the minimum.
Algorithm
- For each possible split point
kfrom 0 to n (inclusive): - Count the number of
'b's ins[0..k-1]. - Count the number of
'a's ins[k..n-1]. - Record the total deletions as the sum of these two counts.
- Return the minimum total deletions across all split points.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2). For each of the n+1 split points, we scan up to n characters. That gives us O(n) work per split, and O(n^2) total.
- Space Complexity: O(1). We only use a few integer variables regardless of input size.
This re-scans the entire string for every split point. Precomputing the counts once makes each split O(1).
Approach 2: Prefix and Suffix Count
Intuition
Instead of re-counting for every split point, precompute the number of 'b's to the left and 'a's to the right using prefix and suffix arrays. Build prefixB[i] = number of 'b's in s[0..i-1], and suffixA[i] = number of 'a's in s[i..n-1]. For split point k, the cost is prefixB[k] + suffixA[k], and we take the minimum over all k. The cost reuses the same definition as the brute force, so the values are identical, but each lookup is now O(1).
Algorithm
- Build a prefix array
prefixBof sizen + 1, whereprefixB[i]= number of'b's ins[0..i-1]. - Build a suffix array
suffixAof sizen + 1, wheresuffixA[i]= number of'a's ins[i..n-1]. - For each split point
kfrom 0 to n, computeprefixB[k] + suffixA[k]. - Return the minimum value.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Three linear passes: one to build prefixB, one to build suffixA, and one to find the minimum.
- Space Complexity: O(n). Two arrays of size n+1 to store the prefix and suffix counts.
The time is O(n), but the two arrays cost O(n) extra space. A single running count removes them.
Approach 3: Single Pass DP (Optimal)
Intuition
Scan the string left to right, maintaining bCount, the number of 'b's seen so far. When we reach an 'a', it sits after every 'b' counted so far, which violates the balanced property. There are two ways to resolve every such conflict in the prefix ending here:
- Delete this
'a': The cost isdeletions + 1, one more than the best cost for the prefix without this character. - Delete all previous
'b's instead: The cost isbCount, the strategy of removing every'b'seen so far so that this'a'(and any later'a') can stay.
Keep a variable deletions holding the minimum deletions that balance the prefix up to the current position. A 'b' adds no new conflict, so it only increments bCount. An 'a' takes the cheaper option: deletions = min(deletions + 1, bCount). This is a space-optimized DP where deletions is the optimal cost for the prefix seen so far.
deletions is the minimum deletions that balance the prefix ending at the current index. Any optimal solution for the prefix ending in this 'a' either deletes this 'a' (cost deletions + 1, building on the best solution for the shorter prefix) or deletes every 'b' seen so far so the 'a's can stay (cost bCount). These two cases cover every optimal solution for the new prefix, so the minimum of them is optimal. bCount is also a hard ceiling: deleting all 'b's always yields a balanced prefix, so the running answer never exceeds it.
Algorithm
- Initialize
deletions = 0andbCount = 0. - For each character in
s: - If
'b': incrementbCount. - If
'a': setdeletions = min(deletions + 1, bCount). - Return
deletions.
Visualization and Code
Loading animation...
- Time Complexity: O(n). Single pass through the string, doing O(1) work per character.
- Space Complexity: O(1). Only two integer variables regardless of input size.