Problem statement

https://leetcode.com/problems/sort-characters-by-frequency/

Solution

We can sort pairs: (frequency, letter) using counter for all string.

Complexity

Time complexity in O(n + m log m), where m is size of alphabet, space complexity is O(m).

Code

class Solution:
    def frequencySort(self, s):
        return "".join([a*b for a,b in Counter(s).most_common()])

Remark

Other approaches:

We can use counters to count frequencies of each element and put them into hash table. Then we can use the fact, that frequencies are never more than n and use buckets: for example if some letter have frequency 3, put it to bucket number 3. Then we traverse buckets from the end and build string. Overall time and space complexity is O(n).

We can also use heaps instead of sort with exaclty the same complexity. In practice, if m is not big, performance can be better than buckets approach.

See also similar problem 0347: Top K Frequent Elements and 0692. Top K Frequent Words.