451. Sort Characters By Frequency.py

class Solution:
    """
    what's distribution of input string s:
        ---> s consists of English letters and digits. At most, 26+10 numbers
        
    Heap solution and Sorting takes O(nlogn)
    
    Bucket sort 
    
    freq array=[0,1,2,3,..,max_freq]
                |            |
                []           [associated char wiht this frequency]
    max_freq at most n+1, it's impossibble to be more than n+1
    So, running time is O(n)
    index represent freqency, and 
    """
    def frequencySort(self, s: str) -> str:
        """
        Heap
        T:O(nlogn)
        """
        counter = collections.Counter(s)
        heap = []
        for char, freq in counter.items():
            heapq.heappush(heap, (-freq, char))
        res = ""
        n = len(heap)
        for i in range(n):
            freq, char = heapq.heappop(heap)
            res+=char*-freq
        return res
    
    def frequencySort(self, s: str) -> str:
        counter = collections.Counter(s)
        n = len(s)
        bucket = [[] for i in range(n+1)] 
        for char, freq in counter.items():
            bucket[freq].append(char)
        res = ""
        for i in range(len(bucket)-1, -1, -1):
            for char in bucket[i]:
                res += char * i
        return res