Code Implementation

class Solution:
    def minimumDeletions(self, s: str) -> int:
        # Count total 'b's in the string
        total_b = s.count('b')
        res = float('inf')
        left_a = 0
        right_b = total_b
        for c in s:
            res = min(res, left_a + right_b)
            if c == 'a':
                left_a += 1
            else:
                right_b -= 1
        res = min(res, left_a + right_b)
        return res
      

class Solution {
public:
    int minimumDeletions(string s) {
        int total_b = 0;
        for (char c : s) if (c == 'b') total_b++;
        int res = INT_MAX, left_a = 0, right_b = total_b;
        for (char c : s) {
            res = min(res, left_a + right_b);
            if (c == 'a') left_a++;
            else right_b--;
        }
        res = min(res, left_a + right_b);
        return res;
    }
};
      

class Solution {
    public int minimumDeletions(String s) {
        int totalB = 0;
        for (char c : s.toCharArray()) if (c == 'b') totalB++;
        int res = Integer.MAX_VALUE, leftA = 0, rightB = totalB;
        for (char c : s.toCharArray()) {
            res = Math.min(res, leftA + rightB);
            if (c == 'a') leftA++;
            else rightB--;
        }
        res = Math.min(res, leftA + rightB);
        return res;
    }
}
      

var minimumDeletions = function(s) {
    let totalB = 0;
    for (let c of s) if (c === 'b') totalB++;
    let res = Number.MAX_SAFE_INTEGER, leftA = 0, rightB = totalB;
    for (let c of s) {
        res = Math.min(res, leftA + rightB);
        if (c === 'a') leftA++;
        else rightB--;
    }
    res = Math.min(res, leftA + rightB);
    return res;
};
      

Problem Description

Given a string s consisting only of the characters 'a' and 'b', your task is to find the minimum number of deletions needed to make s balanced. A string is considered balanced if there is no index i such that s[i] == 'b' and s[j] == 'a' with i < j. In other words, all 'a' characters must appear before any 'b' characters. You can delete any character from the string, and you must determine the smallest possible number of deletions to achieve a balanced string.

• Only deletions are allowed; you cannot rearrange or insert characters.
• Each character can be deleted at most once (do not reuse elements).
• There is always at least one valid solution.

Thought Process

The naive approach would be to try all possible ways of deleting characters to make the string balanced, but this would be very inefficient for long strings. Instead, let's think about what makes a string unbalanced: any 'b' before an 'a' creates a violation. To fix this, we have two options for each violation:

• Delete the 'b' (so no 'b' appears before an 'a'), or
• Delete the 'a' (so no 'a' appears after a 'b').

If we think of splitting the string at every possible position, we can count the number of deletions needed to make everything to the left contain only 'a's and everything to the right only 'b's. Our goal is to find the split that requires the fewest deletions.

Solution Approach

• Step 1: Count the total number of 'b' characters in the string. This will help us track how many 'b's remain on the right as we process the string.
• Step 2: Initialize two counters:
  • left_a: The number of 'a's encountered from the start (these would need to be deleted if we want only 'b's on the left).
  • right_b: The number of 'b's remaining to the right (these would need to be deleted if we want only 'a's on the right).
• Step 3: Iterate through the string, updating left_a and right_b as you go. At each position, calculate the total deletions needed: left_a + right_b.
• Step 4: Keep track of the minimum deletions found at any split point.
• Step 5: After the loop, check the final split (all 'a's to the left, all 'b's to the right) and return the minimum deletions found.

This approach ensures that at every possible split, we efficiently compute the minimum deletions needed to make the string balanced.

Example Walkthrough

Let's use the input s = "aababbab".

1. Count total 'b's: There are 4 (s[2], s[4], s[5], s[7]).
2. Initialize left_a = 0, right_b = 4, res = inf.
3. Iterate through the string:
   • At index 0 ('a'): left_a = 1, right_b = 4, deletions = 0 + 4 = 4, res = 4.
   • At index 1 ('a'): left_a = 2, right_b = 4, deletions = 1 + 4 = 5, res = 4.
   • At index 2 ('b'): left_a = 2, right_b = 3, deletions = 2 + 4 = 6, res = 4.
   • At index 3 ('a'): left_a = 3, right_b = 3, deletions = 2 + 3 = 5, res = 4.
   • At index 4 ('b'): left_a = 3, right_b = 2, deletions = 3 + 3 = 6, res = 4.
   • At index 5 ('b'): left_a = 3, right_b = 1, deletions = 3 + 2 = 5, res = 4.
   • At index 6 ('a'): left_a = 4, right_b = 1, deletions = 3 + 1 = 4, res = 4.
   • At index 7 ('b'): left_a = 4, right_b = 0, deletions = 4 + 1 = 5, res = 4.
4. The minimum deletions needed is 2 (by deleting s[2] = 'b' and s[5] = 'b').

This process ensures we check all possible places to split the string, always keeping the deletions minimal.

Time and Space Complexity

• Brute-force approach: For each subset of characters, check if the result is balanced. This is exponential time, O(2^n), and impractical for long strings.
• Optimized approach (current solution):
  • Time Complexity: O(n) — We make one pass to count 'b's and another pass to compute the minimum deletions.
  • Space Complexity: O(1) — Only a few integer variables are used, regardless of input size.

Summary

The key insight is to recognize that the problem reduces to finding the optimal split point where all 'a's are to the left and all 'b's are to the right. By using prefix sums and tracking the number of 'a's and 'b's, we can efficiently compute the minimum deletions needed in linear time. This approach avoids the need for brute-force checking and demonstrates a powerful use of cumulative counting in string processing.