LC451 Sort Characters By Frequency

class Solution:
    # time O(lgN)  space O(N) 
    # main idea:  Hash Table + Sort 
    def frequencySort(self, s: str) -> str:
        d = dict()
        for i in range(len(s)):
            if s[i] not in d:
                d[s[i]] = 1
            else:
                d[s[i]] += 1
        tups = sorted(d.items(), key=lambda k : k[1], reverse= True )
        res = ''
        for tup in tups:
            res += tup[0] * tup[1] 
        return res

class Solution:
# time O(N) space O(N)
# main idea use bucket sort to replace sort function
    def frequencySort(self, s: str) -> str:
        if not s: return s
        # time O(NlgN) space O(N)
        d = dict() # space O(K)     
        for i in range(len(s)): # time O(N)
            if s[i] not in d:
                d[s[i]] = 1
            else:
                d[s[i]] += 1
        size_bucket = max(d.values())
        bucket = [[] for _ in range(size_bucket +1)] # can't use []* size 
        # fill up bucket 
        for k,val in d.items():
            bucket[val].append(k)
        # fill out res by frequency 
        res = []    
        for i in range(size_bucket,0,-1):
            for each in bucket[i]:
                res.append(each*i)
        return ''.join(res)  # O(N)