InternDoor

Make every letter count different

Mediumgreedy · strings · sortingRead the input, print the output

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.

Example
Input
4
aabbbc
xxyyzz
mmmnnnoo
q
Output
0
3
2
0
  1. a appears 2 times, b 3 times and c once: already all different.
  2. Every letter appears twice. Keep x twice, y once and no z: one y and both z are deleted.
  3. m and n appear 3 times, o twice. Bring n down to 2 and o down to 1.
  4. One letter is always tidy.

Limits

  • 1 <= T <= 100
  • each word holds 1 to 100000 letters
  • all 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

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.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.