is it the best solution?

[blaurent]

In this solution you suggest using a map as table. This will slow down the algorithm to O(N*logN).

The reason is that in the standard solution accesses to the table is O(1). This is the case when the table is hash based or an array. But it's not the case when the table is a map as you suggest. A map is tree based and has O(logN) accesses. One O(N) pass with O(logN) accesses results in an O(N*logN) algorithm (and not O(2*N)).

So the standard solution is hard to beat here. It's O(N) and even with a post-sort step it will be O(N*logN) at the most (when all letters are different but the more repeated letters there are the more it will tend towards O(N)).

Ah yes of course! You're right.

Thanks for the explanation.