Given a string S consisting of N lowercase letters, return the minimum number of letters that must be deleted to obtain a word in which every letter occurs a unique number of times.For Ex - "aaaabbbb" should return 1, as when we delete 1 a or 1 b , a and b will have different frequencies.
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.

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

Question

Given a string S consisting of N lowercase letters, return the minimum number of letters that must be deleted to obtain a word in which every letter occurs a unique number of times.For Ex - "aaaabbbb" should return 1, as when we delete 1 a or 1 b , a and b will have different frequencies.

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.

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

Accepted Answer

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:

Call a helper function to create all the subsequences.
Recursively call 2 functions, one by including the current character and one by excluding the current character.
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:

Create a map to store the frequency of each character.
Traverse the subsequence and store the frequencies in the map.
Create a set.
Traverse the keys of the map and store its frequency in the set.
If the frequency is already in the set then return false.
If all the array is traversed, then return true.

Space Complexity: O(n)Explanation:

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.

Time Complexity: OtherExplanation:

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).

Accepted Answer

Using Max Heap

Create a max heap of integers, which will store the frequency of each character. Initialize a variable ‘count’ that will store the number of deleted characters. Create a map, and store the frequency of each character by traversing the string. Also store all the keys frequency in the heap.

Now, while the heap is not empty, remove the highest occurrence of a character. If the current top element of the heap is equal to the frequency of the highest occurring character then decrement the frequency of the highest occurred character and push it back into the heap if the new frequency is not zero. Increment the 'count' by 1. Finally, return the count.

Space Complexity: OtherExplanation:

O(M), where ‘M’ is the number of unique characters in the string.

Since we will be using extra space to store frequencies of all unique characters in a map of size M and a heap of size M. Thus the space complexity will be O(M).

Time Complexity: O(nlogn)Explanation:

O(N * log M), where ‘N’ is the length of the string and ‘M’ is the number of unique characters in the string.

Since we are traversing the complete string in (O(N)) time. The complexity of counting of the characters to remove is O(log(M)) for each of the character. Thus, the overall complexity would be O(N * logM).