Though O(N*log(N)) and O(N) both gave me 0.068 timing, it's a good testdata to write such code, would matter if N could be up to 10^6. Also this solution with O(1) stepping may additionally report number of ways to achieve minimal result.

The structure is doubly-linked list of available amounts (always strictly ascending), each of which is non-empty doubly-linked list of characters with that amount. This structure allows to query for max and to change amount of single character +-1 at O(1).