Minimum Deletions

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
7 upvotes
Asked in company
Adobe

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
aabbbab
aabbbb
Sample Output 1 :
1
0
Explanation For Sample Output 1 :
For test case 1 :
You can delete character ‘a’ at the 5th index to make the string balanced ("aabbbab" -> "aabbbb"). Hence, the answer is 1.

For test case 2 :
The given string is already balanced, so no operations are needed. Hence the answer is 0.
Sample Input 2 :
2
bbaaabb
aaaabba
Sample Output 2 :
2
1
Hint

Try to think of an approach by using recursion.

Approaches (3)
Recursion

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
  1. 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.
  2. 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.
Time Complexity

O(N^2), where ‘N’ is the length of String ‘Str’.

 

At each index, we are also calculating the number of ‘a’ ahead, we are doing N^2 operations. Hence the overall time complexity will be O(N^2).

Space Complexity

O(N), where ‘N’ is the length of String ‘Str’.

 

The recursion stack requires O(N) space. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Minimum Deletions
Full screen
Console