Make every letter count different
Reported in interviews at (where)
A word is tidy when no two of the letters in it appear the same number of times. A letter that has been deleted completely no longer counts.
For each word, find the fewest letters you must delete to make it tidy.
Input
The first line holds T, the number of tests. Each test is one line holding one word of lowercase letters.
Output
For each test, one line: the fewest letters to delete from its word.
- Input
4
aabbbc
xxyyzz
mmmnnnoo
q- Output
0
3
2
0
- a appears 2 times, b 3 times and c once: already all different.
- Every letter appears twice. Keep x twice, y once and no z: one y and both z are deleted.
- m and n appear 3 times, o twice. Bring n down to 2 and o down to 1.
- One letter is always tidy.
Limits
1 <= T <= 100each word holds 1 to 100000 lettersall the words together hold at most 400000 letters
Hints
Hint 1
Only the counts matter, not which letter has which. Sort the 26 counts from largest to smallest.
Hint 2
Go down the sorted counts: each may keep at most one less than the count kept before it, and never less than 0. Whatever it cannot keep is deleted.
Where this was reported
- American Express, Tech intern on-campus interview, 2020 (GeeksforGeeks)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
