• Posts

Problem 1653 Minimum Deletions to Make String Balanced

Problem Statement

Link - Problem 1653

Question

You are given a string s consisting only of characters 'a' and 'b'​​​​.

You can delete any number of characters in s to make s balanced. s is balanced if there is no pair of indices (i,j) such that i < j and s[i] = 'b' and s[j]= 'a'.

Return the minimum number of deletions needed to make s balanced.

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'​​.

Solution

class Solution {
public:
    int minimumDeletions(string s) {
       int size = s.size();
       int aCnt = 0;
       int bCnt = 0;

       for(auto &ch:s)
        if(ch=='a')
            aCnt++;

        int del = size;

        for(auto &ch:s){
            if(ch=='a')
                aCnt--;
            del = min(del,aCnt+bCnt);
            if(ch=='b')
                bCnt++;
        }

        return del;
    }
};

Complexity Analysis

| Algorithm                | Time Complexity | Space Complexity |
| ------------------------ | --------------- | ---------------- |
| Single-pointer traversal | O(n)            | O(1)             |

Explanation

Intial Thoughts

To approach this problem, we should first understand what makes a string balanced. A string is balanced if there are no pairs of characters where ‘b’ comes before ‘a’. We should look for patterns or sequences in the string that violate this rule. We can think of it like trying to get all the ‘b’s to the right of all the ‘a’s, which can be visualized as a sorting process but with the option to delete characters instead of just rearranging them. This suggests a strategy of tracking the counts of ‘a’ and ‘b’ as we scan through the string and finding the minimum number of deletions needed to achieve balance.

Intuitive Analysis

Intuitively, solving this problem involves scanning the string and keeping track of the counts of ‘a’s and ‘b’s. We should think of it in terms of maintaining a balance between ‘a’s and ‘b’s as we move through the string. The key insight is to realize that the minimum number of deletions will occur at the point where the string becomes balanced with the fewest deletions. We can use variables to keep track of the number of ‘a’s and ‘b’s encountered so far and the minimum number of deletions required up to that point. This approach allows us to methodically consider each character in the string and determine how it affects our goal of achieving a balanced string with the minimum number of deletions.

1. Intuition

• The problem requires finding the minimum number of deletions to make the string balanced, meaning no ‘b’ appears before ‘a’.
• To approach this, we need to consider the counts of ‘a’ and ‘b’ in the string and how they change as we iterate through it.
• The key insight is to track the counts of ‘a’ and ‘b’ and find the minimum number of deletions required at each step.
• We can use a single pass through the string to calculate the minimum deletions, making the solution efficient.
• The solution works by maintaining a running count of ‘a’ and ‘b’ and updating the minimum deletions based on these counts.
• The algorithmic choice of using a single pass and updating counts in-place makes the solution space-efficient.
• By considering all possible deletions and choosing the minimum, we ensure the solution is optimal.

2. Implementation

• We start by initializing size, aCnt, and bCnt variables to keep track of the string size and ‘a’ and ‘b’ counts.
• The for loop iterates over the string, incrementing aCnt when ‘a’ is encountered, and bCnt when ‘b’ is encountered.
• We use del to store the minimum number of deletions, initially set to the string size, and update it as we iterate through the string.
• Inside the loop, we update aCnt and bCnt based on the current character and calculate the minimum deletions using min(del, aCnt + bCnt).
• The return del statement provides the minimum number of deletions required to make the string balanced.
• The use of auto &ch:s allows us to iterate over the string characters efficiently, and min(del, aCnt + bCnt) ensures we always choose the minimum deletions.
• The overall implementation has a time complexity of O(n), where n is the string size, making it efficient for large inputs.

Complexity Analysis

Time Complexity:

• The time complexity of the given code is O(n) because it involves a single-pointer traversal of the string s twice: once to count ‘a’s and once to calculate the minimum deletions, where n is the size of the string.
• The dominant operation is the iteration over the string s using for(auto &ch:s), which is performed twice, resulting in a linear time complexity.
• The Big O classification of O(n) is justified because the time complexity grows linearly with the size of the input string, and there are no nested loops or recursive calls that would increase the complexity to a higher order.

Space Complexity:

• The space complexity of the given code is O(1) because it only uses a constant amount of space to store the variables size, aCnt, bCnt, and del, regardless of the size of the input string s.
• The impact of the data structures used is minimal, as only a few integer variables are used, and there are no data structures that grow with the size of the input, such as arrays or linked lists.
• The justification of space complexity O(1) is due to the fact that the memory usage does not increase with the size of the input, and the code does not allocate any additional memory that scales with the input.

Footnote

This question is rated as Medium difficulty.

Hints

You need to find for every index the number of Bs before it and the number of A’s after it

You can speed up the finding of A’s and B’s in suffix and prefix using preprocessing

Similar Questions: