Make Every Letter Count Distinct
MediumGreedy
Problem
A word is tidy when no two different letters appear the same (non-zero) number of times. For example, "aabbbc" is tidy (counts 2, 3, 1) but "aabb" is not.
Return the minimum number of characters you must delete from word to make it tidy.
Example 1
- Input:
- word = "aaabbbcc"
- Output:
- 2
Counts 3, 3, 2. Delete one b and one c to get counts 3, 2, 1.
Example 2
- Input:
- word = "ceabaacb"
- Output:
- 2
Counts a:3, b:2, c:2, e:1. Lower one count from 2 to 1 and another from 1 to 0.
Constraints
- 1 ≤ word.length ≤ 10^5
- word contains only lowercase English letters
Hint
Show the first hint
Only the multiset of letter counts matters.
Walkthrough
How to approach it
01Clarify before coding
- Is deleting a letter entirely (count 0) allowed? Yes; zero counts do not clash.
- Do we only delete, never add? Only delete.
- Only lowercase letters? Yes, so at most 26 counts.
02Brute force
Try every combination of target counts (0 … count) for each letter and keep the cheapest tidy one.
Cost: Product of (count + 1) over letters: exponential.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.