Minimum Character Deletion

Moderate
0/80
Average time to solve is 15m
26 upvotes
Asked in companies
American ExpressDeutsche BankMeesho

Problem statement

You are given a string ‘STR’. You need to find and return the minimum number of characters to be deleted from ‘STR’ so that the frequency of each character in the string becomes unique.

Example: 
If the given string is “aaBBccc” then the frequency of characters: { a:2, B:2, c:3 }. Now, as ‘a’ and ‘B’ both have the same frequency 2, we need to delete one character either one ‘a’ or one ‘B’, to make their frequency different. After deleting any character we will get frequency as 1,2 and 3, as they all are different. Thus we got our solution as 1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains a string 'STR'.
Output Format: 
For each test case, print an integer denoting the minimum number of characters to be deleted from the string 'STR'.
Note: 
You are not required to print the output, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= |STR| <= 10^5

Where |STR| is the length of the string 'STR'.

Time limit: 1 sec
Sample Input 1:
2
aaabbbcc
pqr
Sample Output 1:
2
2
Explanation for output 1:
In test case 1, after removing 2 a’s or 2 b’s, the resulting string that formed will have distinct frequencies of each character. 

In test case 2, we need to remove any two characters from the string to make a unique frequency string.
Sample Input 2:
2
AAbbbC
yxyzyzz
Sample Output 2:
0
1
Explanation for Output 2:
In test case 1, as the frequency of each character is already unique, thus no need to delete any character.

In test case 2, remove any 1 of the occurrence of y or z, and then we can each character's frequency as unique.
Hint

For every subsequence of the given string, check whether the frequency of all the characters is unique or not.

Approaches (2)
Brute Force

As we are only allowed to delete the character, thus the resulting string after deletion of some character would be the subsequence of the string. So, we have to find such a subsequence which has the unique frequency of each character. 

 

Initialise a variable ‘ans’ that will store the minimum number of characters that are needed to remove from the string. Create all the subsequences of the string and check whether it satisfies the condition, simultaneously update the ‘ans’ with the minimum of ‘ans’ and ('N' - length of subsequence). Finally, return the ‘ans’.

 

For creating the subsequence of string:

 

  1. Call a helper function to create all the subsequences.
  2. Recursively call 2 functions, one by including the current character and one by excluding the current character.
  3. The base case would be when input length becomes zero, then check for the condition of unique frequency of character and update the ans accordingly.

 

For checking the unique frequency condition:

 

  1. Create a map to store the frequency of each character.
  2. Traverse the subsequence and store the frequencies in the map.
  3. Create a set.
  4. Traverse the keys of the map and store its frequency in the set.
  5. If the frequency is already in the set then return false.
  6. If all the array is traversed, then return true.
Time Complexity

O(N * 2^N), where ‘N’ is the length of the string.

 

Since for every index of the given string, we have 2 choices i.e either to include that character or exclude the character. And we are traversing each subsequence to store frequencies that will take O(N) time. Thus, the overall time complexity would be O(N * 2^N).

Space Complexity

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

 

Since we are storing N subsequences of the string in the stack space and extra space is also required to store the characters in the map.

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