Last Updated: 12 Apr, 2021
Minimum Deletions To Make Character Frequencies Unique
Moderate
Asked in companies
You are given a string ‘STR’ consisting of lowercase English alphabets. Your take is to find out the minimum number of character deletions required such that each character in the final string has a unique frequency.
Input Format :
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow.
The first line of each test case contains a single string ‘STR’ denoting the initial string.
Output Format :
For each test case, print a single integer, denoting the minimum number of character deletions required such that each character in the final string has a unique frequency.
Output for each test case will be printed in a separate line.
Note :
You don’t have to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
2 <= |STR| <= 10^5
Where |STR| denotes the length of the initial string ‘STR’.
Time limit: 1 second
Approaches
- We need to think greedily. For each character in the initial string ‘S’, count its frequency. Let’s call this frequency array as ‘FREQ[26]’, the size of this array will be 26 as the string only consists of lowercase English alphabets.
- Then we need to count how many characters have the same frequency. To do that, create an array ‘COUNT[N+1]’, where ‘COUNT[i]’ denotes how many characters have frequency ‘i’. For i goes from 0 to 26 increase ‘count[freq[i]]’ by 1.
- If ‘COUNT[i]’ is greater than 1, that means more than 1 characters, at this instant, have equal frequency(which is equal to i). Hence in those cases we need to delete ‘COUNT[i] - 1’ characters and increase ‘COUNT[i-1]’ by ‘COUNT[i] - 1’.
- Repeat the above step for ‘N’ times.
- The answer is the sum of the number of deletions we made in the ‘COUNT’ array.