Minimum Deletions to Make String Balanced

Problem Statement

In this problem, you are given a string consisting solely of the characters 'a' and 'b.' Your task is to transform the string into a balanced version by removing as few characters as possible. A string is considered balanced when it does not contain any instance where a 'b' precedes an 'a' across any pair of indices (i, j) such that i < j. The challenge is to compute the minimum number of deletions required to make the string balanced.

Examples

Example 1

Input:

s = "aababbab"

Output:

2

Explanation:

You can either:
Delete the characters at 0-indexed positions 2 and 6 ("aababbab" -> "aaabbb"), or
Delete the characters at 0-indexed positions 3 and 6 ("aababbab" -> "aabbbb").

Example 2

Input:

s = "bbaaaaabb"

Output:

2

Explanation:

The only solution is to delete the first two characters.

Constraints

• 1 <= s.length <= 105
• s[i] is 'a' or 'b'​​.

Approach and Intuition

To solve the problem of making the string balanced with the minimum deletions, an intuitive approach involves a dynamic thought process that wrestles with the arrangement of 'a's and 'b's in the string:

1. Traverse the string and track the count of 'a' characters, as one potential solution could be to remove all 'b' characters before the first occurrence of 'a'.

2. Similarly, count the 'b' characters, since removing all 'a' characters after the last occurrence of 'b' might also yield a balanced string.

3. However, a more subtle approach takes into account the edge cases:

   • Iterate through the string while maintaining a dynamic count of the deletions required if you were to split the string into two parts at that point:
     • All 'b's to the left of the current index.
     • All 'a's to the right of the current index.
   • You compute the deletions needed for every index and track the minimum encountered through the iteration.

4. This approach balances considering all segments of the string dynamically, allowing the identification of the least disruptive (in terms of deletions) point to divide the string. This helps achieve a globally optimal solution that respects the local conditions at each step of the iteration.

This method leverages a combination of dynamic computation and greedy strategies, ensuring that we handle both straightforward and complex string configurations effectively. The goal is a fully balanced string with minimized deletions, thereby preserving as much of the original string as possible while adhering to the balance constraint.

Solutions

class Solution {
public:
    int minRemovals(string s) {
        int size = s.size();
        int del = 0;
        int countB = 0;
            
        for (int i = 0; i < size; i++) {
            if (s[i] == 'b') {
                countB++;
            } else {
                del = min(del + 1, countB);
            }
        }
    
        return del;
    }
};