def frequencySort(self, s):
ctr = Counter(s)
list = [(val, key) for key,val in ctr.items()]
heapq.heapify(list); result = []
while (len(list) > 0) :
val, key = heapq.heappop(list)
result += [key] * val
return ''.join(result)
Python O(NlogN) solution using heap  7 lines

@intelaka my bad, yeah the popping is O(nlogn) but heapify is O(n). We can probably have an O(n) solution using bucket sort