Last Updated: 29 Aug, 2021
Minimum Deletions
Moderate
Asked in company
You are given a string ‘Str’ consisting of only characters ‘a’ and ‘b’. You can delete any number of characters in ‘Str’ to make ‘Str’ balanced.
A string is called balanced if there is no pair of indices (i, j) such that i < j, Str[i] = ’b’ and Str[j] = ’a’. You have to return the minimum number of deletions to make the ‘Str’ balanced.
For example:
Consider the string 'Str' = “aabbbab”, you can delete character ‘a’ at the 5th index to make the string balanced ("aabbbab" -> "aabbbb"). Hence, the answer is 1.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows.
The first line of each test case contains a string ‘Str’ representing the given string.
Output Format :
For each test case, print a single integer representing the minimum number of deletions needed to make ‘Str’ balanced.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1<= T <= 10
1 <= |Str| <= 10^6
Str[i] contains only characters 'a' and 'b'.
Time limit: 1 sec
Approaches
Let’s take a decision on the current character of the string and let recursion do the rest of the work. We will create a helper function to do the task.
Algorithm:
- In the given string ‘Str’ check the first character:
- If the first character is ‘a’, then we will add it to our answer. There is no need to delete it because we want the string in the form of “aaa...bbb...bb”.
- Else if the current character is ‘b’, then we have two choices
- Either delete this character and pass the rest of string to recursion. If we delete it, then the number of deletion operations will be incremented by 1.
- Otherwise, let’s assume that from now on, we only require ‘b’, so all the ‘a’ characters are to be deleted, which are ahead. Hence deletion operation will be increment by the number of ‘a’ characters in front.
- Minimum of these 2 operations will be the answer.
The approach will be the same as what we did in the recursive brute force approach. But this time, we will count the number of ‘a’ ahead for each index ‘i’ before calling recursion.
Algorithm:
- In the given string ‘S’ check the first character:
- If the first character is ‘a’, then we will add it to our answer. There is no need to delete it because we want the string in the form of “aaa...bbb...bb”.
- Else if the current character is ‘b’, then we have two choices
- Either delete this character and pass the rest of the string to recursion. If we delete it, then the number of deletion operations will be incremented by 1.
- Otherwise, let’s assume that from now on, we only require ‘b’, so all the ‘a’ characters are to be deleted, which are ahead. Hence deletion operation will be increment by the number of ‘a’ characters in front. Now we have pre-calculated the number of ‘a’ characters ahead for each index ‘i’. Hence we don’t have to iterate over to count the number of occurrences of ‘a’.
- Minimum of these 2 operations will be the answer.
Let’s solve this problem backward. Instead of deleting characters from the string, let’s think about the possible strings that we can make, for example, whatever string ‘S’ has been given to us, we know that we ultimately want it in the form of “aaa...bbb...bb”
So using this idea, let’s take an initial String ‘T’ = “bbb...bb”, and check the minimum number of operations required to make the current string ‘Str’ = ‘T’.
After that, we will iterate at each character and try to convert our string ‘T’ to
- at the first iteration :
- “abbb...bb”
- at second iteration :
- “aabbb...bb”
And so on.
So at each iteration, we can easily calculate the operations required to make string ‘S’ = ‘T”, minimum of all the operations is going to be our answer.
Algorithm:
- Let’s maintain a variable named ‘answer’ and initialize it to 0.
- Initially, when we assumed our String ‘T’ = “bbbb………”, then the total number of operations required to make our string ‘Str’ = ‘T’ are the number of occurrences of character ‘a’. Let the number of occurrences of the character ‘a’ be ‘occurrences’.
- We will maintain a variable ‘answer’ to store our required answer. We will initialize ‘answer’ as ‘occurrences’.
- We will iterate ‘i’ through the string ‘S’.
- If ‘Str[i]’ is equal to ‘a’.
- Decrement ‘occurrences’ by 1
- Else
- Increment ‘occurrences’ by 1
- Update ‘answer’ as the maximum of ‘answer’ and ‘occurrences’.
- If ‘Str[i]’ is equal to ‘a’.
- The ‘answer’ is our required answer.
Similar problems