Minimum Character Deletion Problem Statement

You have been provided a string STR. Your task is to find and return the minimum number of characters that need to be deleted from STR so that each character's frequency in the string is unique.

Example:

Input:

STR = "aaBBccc"

Output:

1

Explanation:

The frequency of characters: {a:2, B:2, c:3}. Both 'a' and 'B' have the same frequency of 2. By removing one character, either 'a' or 'B', their frequencies become different resulting in {1, 2, 3}, which are all unique.

Input:

"T" - Number of test cases.
For each test case: A string "STR".

Output:

An integer for each test case, representing the minimum number of deletions required to make all character frequencies in 'STR' unique.

Constraints:

1 ≤ T ≤ 10

1 ≤ |STR| ≤ 10⁵

Question

Minimum Character Deletion Problem Statement

You have been provided a string STR. Your task is to find and return the minimum number of characters that need to be deleted from STR so that each character's frequency in the string is unique.

Example:

Input:

STR = "aaBBccc"

Output:

Explanation:

The frequency of characters: {a:2, B:2, c:3}. Both 'a' and 'B' have the same frequency of 2. By removing one character, either 'a' or 'B', their frequencies become different resulting in {1, 2, 3}, which are all unique.

Input:

"T" - Number of test cases.
 For each test case: A string "STR".

Output:

An integer for each test case, representing the minimum number of deletions required to make all character frequencies in 'STR' unique.

Constraints:

1 ≤ T ≤ 10
1 ≤ |STR| ≤ 10⁵

Accepted Answer

Minimum Character Deletion

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

Sample Input 1:

2

aaabbbcc

pqr

Sample Output 1:

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.

in java