A collector keeps every trading card on a single long shelf, described as a string s of lowercase English letters: each character is one card, and its letter names that card's type, so the number of times a letter appears in s is exactly how many copies of that card type currently sit on the shelf. The collector may repeatedly perform two kinds of shelf actions, each counting as one operation: discard one card (remove a single occurrence of any chosen letter from s), or acquire one card (insert a single occurrence of any chosen lowercase letter anywhere into s). The collector wants to reach a shelf where every card type that is still present appears in exactly the same quantity as every other card type that is still present -- a card type that has been discarded down to zero copies is simply gone and places no requirement on anyone. Determine the minimum number of shelf operations needed to reach such a shelf.
Print a single integer: the minimum number of operations required.
Example 1
Input
3 aab
Expected
1
Explanation
The shelf holds letter counts a=2, b=1. Discarding one 'a' leaves a=1, b=1, so every remaining type appears once -- a single operation suffices, and no cheaper option exists.
Example 2
Input
5 aaabb
Expected
1
Explanation
The shelf holds a=3, b=2. Discarding one 'a' leaves a=2, b=2, matching in exactly one operation (acquiring one 'b' instead, raising it to 3, would also cost one operation); either way the minimum is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →