LeetCode 1653: Minimum Deletions to Make String Balanced

Explanation:

To make the string balanced, we need to delete characters such that there are no occurrences of "ba" in the string. We can achieve this by iterating through the string and keeping track of the number of 'a's encountered so far. Whenever we encounter a 'b', we have two choices: either delete the 'b' or delete the last 'a' encountered. We choose the option that minimizes the number of deletions needed.

Algorithm:

1. Initialize a variable aCount to keep track of the number of 'a's encountered so far.
2. Initialize a variable deletions to 0 to keep track of the number of deletions needed.
3. Iterate through the string:
   • If the current character is 'a', increment aCount.
   • If the current character is 'b':
     • If there are 'a's encountered before, decrement aCount and increment deletions.
     • If there are no 'a's encountered before, increment deletions.
4. Return the final value of deletions.

Time Complexity:

The time complexity of this algorithm is O(n), where n is the length of the input string s.

Space Complexity:

The space complexity of this algorithm is O(1) as we are using a constant amount of extra space.

:

class Solution {
    public int minimumDeletions(String s) {
        int aCount = 0;
        int deletions = 0;
        
        for (char c : s.toCharArray()) {
            if (c == 'a') {
                aCount++;
            } else {
                if (aCount > 0) {
                    aCount--;
                } else {
                    deletions++;
                }
            }
        }
        
        return deletions;
    }
}