A word is balanced if no two different letters occur the same (non-zero) number of times. You may delete characters from word. Return the minimum number of deletions that makes it balanced. Letters deleted completely no longer count.
Examples
Input: word = "aaabbbcc"
Output: 2
Explanation: Counts are a:3, b:3, c:2. Delete one b (b:2) and one c (c:1): 3, 2, 1.
Input: word = "ppqqrr"
Output: 3
Explanation: Counts 2, 2, 2 must become 2, 1, 0.
Constraints
0 <= len(word) <= 10**5, lowercase letters only.- Target complexity: O(n) to count plus O(26 log 26) to fix the counts.
Goals
- Reduce the problem to a list of letter frequencies
- Lower clashing frequencies to the next free value, as little as possible
- Recognise that a frequency may drop all the way to zero