bucket sort steps:
— spread the elements into buckets
— sort each bucket
— combine the buckets
from collections import defaultdict
class Solution:
def frequencySort(self, s: str) -> str:
#Write your code here
# bucket sort is :
# spread the inputs into buckets
# sort each bucket individually
# Combine all the sorted buckets#count the frequency of each letter, use the dictionary for it
dic = defaultdict(int)
mx = 0
for ch in s:
dic[ch]+=1
if mx < dic[ch]:
mx = dic[ch]# find the max value of frequency , find max value is combined in above loop
# Create a list of lists for managing buckets
bkts = [[] for _ in range(mx+1)]#spread the letters into buckets
for key, val in dic.items():
bkts[val].append(key)# sort each bucket
for bkt in bkts:
if len(bkt)> 1:
bkt.sort()# combine the elements
res = []
for ii in range(mx,0,-1):
for ch in bkts[ii]:
res.extend([ch] * ii)#convert the list to string
return “”.join(res)
