Make every count different
The fewest deletions so no two letters appear the same number of times. About 12 minutes.
Facts about facts
Sometimes you need facts about the items (how many a's are there?), and then facts about those facts (which counts are already taken?). Each kind of fact can live in its own map or set.
So first count, then turn your attention to the counts themselves. It's a two-step way of thinking that shows up in more problems than you'd expect.
- used
- {}
- deletions
- 0
Facts about letters: a 3, b 3, c 2. Now facts about the facts: which counts are taken?
Counts are a 3, b 3 and c 2. You've already given a the count 3 and c the count 2. You delete one b, bringing it to 2. Is 2 free?
- ANo, c has it: b drops to 1
- BYes, 2 is free
- Cb is still 3
Show the answer
No, c has it: b drops to 1. 2 is already taken by c, so b needs one more deletion.
Make every count different
You may delete characters from a lowercase string. Return the fewest deletions needed so that no two letters that remain appear the same number of times.
s = "aaabbbcc" → 2
0 ≤ length ≤ 100,000 · only a to z