Minimum Deletions to Make String Balanced

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;
    }
};

This solution addresses the problem of finding the minimum number of deletions required to make a given string balanced. The string is balanced when all 'a's appear before any 'b' in the string without requiring the characters to be consecutive, but simply non-decreasing order.

Key steps in the provided C++ solution are:

1. Initialize size as the length of the string s.
2. Initialize del to 0, which will keep track of the minimum deletions needed.
3. Initialize countB to 0 to count the occurrences of 'b'.
4. Use a loop to iterate through each character of the string. If the character is 'b', increment countB. If it's 'a', update del using the formula min(del + 1, countB). This step essentially calculates whether removing the current 'a' or already counted 'b's results in fewer deletions.
5. Return the value of del, representing the minimum number of deletions required to balance the string.

This approach efficiently calculates the minimum deletions in a linear pass through the string based on the character analysis and updates the count accordingly. It is both time-efficient and straightforward, utilizing simple arithmetic and comparison operations to achieve the desired result.

class Solution {

    public int minRemovals(String str) {
        int length = str.length();
        int deletionsNeeded = 0;
        int countB = 0;

        for (int i = 0; i < length; i++) {
            if (str.charAt(i) == 'b') {
                countB++;
            } else {
                deletionsNeeded = Math.min(deletionsNeeded + 1, countB);
            }
        }

        return deletionsNeeded;
    }
}

This solution addresses the problem of finding the minimum number of deletions required to make a string "balanced." A balanced string in this context is one where all characters 'a' appear before any character 'b'. The provided Java implementation offers an efficient approach to this problem.

The function minRemovals(String str) within the Solution class performs the following steps:

1. Initialize variables length to store the length of the string, deletionsNeeded to keep track of the deletions required, and countB to count the number of 'b' characters encountered.
2. Loop through each character of the string using a for loop that iterates based on the string’s length.
   • Within the loop, check if the current character is 'b'. If it is, increment the countB variable.
   • If the current character is not 'b', calculate the minimum deletions needed so far. This is done by comparing the current number of deletions needed plus one (to potentially delete the current 'a') against the count of 'b' characters already passed. This uses Math.min() to keep the smaller value.
3. Return the deletionsNeeded at the end of the function, which represents the minimum number of deletions required to make the string balanced.

This algorithm efficiently determines the required deletions by only making a single pass through the string, ensuring a time complexity of O(n), where n is the length of the string. Its space complexity is O(1) as it uses only a few additional variables regardless of the string size. The approach is a blend of tracking seen characters and calculating the minimum steps required dynamically, a typical pattern in problems involving balancing or rearranging characters under constraints.

class Solution:
    def minDelOperations(self, input_str: str) -> int:
        length = len(input_str)
        min_ops = 0
        count_b = 0

        for char in input_str:
            if char == "b":
                count_b += 1
            else:
                # Determine whether to delete 'a' or to retain it
                min_ops = min(min_ops + 1, count_b)

        return min_ops

This Python solution addresses the problem of finding the minimum number of deletions required to make a string balanced. The string is balanced when all characters 'a' are followed only by characters 'b', with no 'a' occurring after a 'b'.

The function minDelOperations takes an input_str as its parameter and executes the following steps:

1. Initialize length to store the length of input_str.
2. Set min_ops to 0, which will count the minimum deletions needed.
3. Initialize count_b to 0 to tally the number of 'b's encountered.

• Iterate through each character in input_str:
  • If the character is 'b', increment count_b.
  • If it's 'a', compute the minimal operations by deciding whether to increment min_ops (indicating deletion of 'a') or to take the current count of 'b's. This choice ensures the smallest number of deletions up to that point in the string.

Return min_ops, which indicates the minimum deletions necessary to ensure the string is balanced.

This algorithm is efficient as it passes through the string only once, thus having a time complexity of O(n), where n is the length of the string.