Leetcode - Sort Characters By Frequency (Python)

May 2020 Leetcode Challenge
Leetcode - Sort Characters By Frequency (Python3)

[edwardteach]

Python implementation in O(n) time instead of using the heap:

class Solution(object):
def frequencySort(self, s):
"""
:type s: str
:rtype: str
"""
count = collections.Counter(s)
new_count = collections.defaultdict(list)

for key, count in count.items(): # basically a bucket count
new_count[count].append(key)

ans = []
for i in range(len(s), -1, -1):
if i in new_count:
for value in new_count[i]:
ans.append(value * i)
return "".join(ans)

[sidheshwar]

We could simply use the most_common() function to do that

class Solution:
def frequencySort(self, s: str) -> str:
output=""
count = Counter(s).most_common()
for c, v in count: output+=c*v
return output