LC 0451 [M] Sort Characters By Frequency - ALawliet/algorithms GitHub Wiki

bucket sort: O(n)

class Solution(object):
    def frequencySort(self, s):
        counter = Counter(s)
        
        max_bucket = max(counter.values())
            
        buckets = [[] for _ in range(max_bucket + 1)]
        for c, count in counter.items():
            buckets[count].append(c)
        
        res = []
        for i in range(len(buckets) - 1, -1, -1):
            for c in buckets[i]:
                res.append(c * i)
        return ''.join(res)

sort hashmap: O(nlogn)

class Solution:
    def frequencySort(self, s: str) -> str:
        counter = Counter(s)
        sort_key = lambda c: (counter[c], c)
        sorted_s = sorted(s, key=sort_key, reverse=True)
        return ''.join(sorted_s)