585. Unique Frequencies
A label printer keeps a string s of visible ASCII characters (codes 33 to 126). To make the tape easy to scan, the shop wants every character that appears on it to appear a different number of times: no two distinct characters may share the same count.
The printer can only erase characters, one occurrence at a time, from any position. Erasing every copy of a character is allowed, and a character that no longer appears has count 0 and is ignored by the rule, so any number of characters may disappear.
Return the minimum number of characters that must be erased. Because the answer depends only on the multiset of counts, the intended solution runs in O(n) time with O(1) extra space (the alphabet has 94 symbols).
Example 1
- Input:
- s = "aaabbbcc"
- Output:
- 2
- Explanation:
The counts are 3, 3 and 2; erasing one b and one c makes them 3, 2 and 1, so two erasures are needed.
Example 2
- Input:
- s = "wxyz"
- Output:
- 3
- Explanation:
All four characters appear once, so erase three of them (or leave one) to keep only a single distinct count.
Example 3
- Input:
- s = "kkkkjjjhhf"
- Output:
- 0
- Explanation:
The counts 4, 3, 2 and 1 are already all different, so nothing is erased.
Constraints
- 1 ≤ s.length ≤ 106
- every character of
shas ASCII code between 33 and 126 (no spaces)
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n + k log k), k = alphabet size
- Space
- O(k)