This is faster approach leveraging counting sort algorithm,
whose complexity is linear; O(n), where n = len(s)
It may not be evident that algorithm below is linear, given the
intrinsic nested loops (3 levels). But one way to look at that,
is that we are imposing a tree structure of 2 levels above the list.
On the first level we are grouping per frequency, and on the
second level we group by character. At the bottom level we have
a permutation of the list itself.
Therefore, regardless of how many levels the tree structure above has,
ultimately the dominating factor is the bottom level (recall
for example that leaves level in a full binary tree, has as much
data as the rest of the tree). The bottom level in our imaginary
tree has as many elements as the list (size n); hence the dominating
factor in the nested loops is n itself (adding the extra cost of the
above layers would make cost a multiple of n, leading to O(n)).
Note: the original count sort algorithm may assume a fixed range
in the values, and iterate through that range. Here we are doing
an small optimization, by iterating only over the observed sub-range
in the list.
from collections import defaultdict from itertools import imap class Solution(object): def frequencySort(self, s): hist = defaultdict(lambda: 0) for c in s: hist[c] += 1 cnt = defaultdict(lambda: ) min_k, max_k = len(s), 0 for c, k in hist.iteritems(): cnt[k].append(c) min_k = min(min_k, k) max_k = max(max_k, k) sorted_s = '' for k in xrange(max_k, min_k - 1, -1): if k in cnt: sorted_s += ''.join(imap(lambda c: c * k, cnt[k])) return sorted_s