Minimum Deletions to Make String Balanced

Leetcode Problem:

• Minimum Deletions to Make String Balanced

Summary

• Find the minimum number of deletions needed to make a string of 'a's and 'b's balanced.

Approach

• Use a greedy approach to count the minimum number of deletions
• Iterate through the string, incrementing the count of 'b's and decrementing the count of 'a's when a 'b' is encountered after an 'a'
• The number of deletions is the minimum between the current count of 'b's and 0.

Complexity

• O(n), where n is the length of the string.

Explain

• The provided C++ code initializes a variable to store the minimum number of deletions and another variable to count the number of 'b's encountered so far
• It then iterates through the string, incrementing the 'b' count when a 'b' is encountered and decrementing the 'a' count when a 'b' is encountered after an 'a'
• The number of deletions is the minimum between the current 'b' count and 0
• This approach ensures that the minimum number of deletions is achieved by deleting the maximum number of 'a's after a 'b' has been encountered.

Solution Code:

class Solution {
public:
    int minimumDeletions(string s) {
        int ans = 0;
        int b_cnt = 0;
        for(int i = 0 ; i < s.size(); i++){
            if(s[i] == 'b'){
                b_cnt++;
            } else if (b_cnt > 0 && s[i] == 'a'){
                ans++;
                b_cnt--;
            }
        }
        return ans;
    }
};