Unique Frequency Deletions
MediumGreedy · Microsoft
You are given a string s of lowercase English letters. The frequency of a letter is how many times it appears in the string.
Delete as few characters as possible so that no two different letters that are still in the string have the same frequency. A letter whose every copy has been deleted no longer appears, so it does not count (frequency 0 never causes a clash).
Return the minimum number of characters you need to delete.
Example 1
- Input:
- s = "aabbccdd"
- Output:
- 5
- Explanation
- All four letters appear twice. One letter can keep 2, one can drop to 1 (1 deletion), and the other two must be deleted completely (2 deletions each): 1 + 2 + 2 = 5.
Example 2
- Input:
- s = "aaaaaaaaaabbbccc"
- Output:
- 1
- Explanation
- The frequencies are 10, 3 and 3. Deleting one
cmakes them 10, 3 and 2, which are all different.
Example 3
- Input:
- s = "abc"
- Output:
- 2
- Explanation
- Each letter appears once. One can stay, and the other two have to be removed entirely, so 2 deletions.
Constraints
- 1 ≤
s.length≤ 105 scontains only lowercase English letters