Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string. Return the sorted string. If there are multiple answers, return any of them.
Example 1: Input: s = “tree” Output: “eert” Explanation: ‘e’ appears twice while ‘r’ and ’t' both appear once. So ‘e’ must appear before both ‘r’ and ’t'. Therefore “eetr” is also a valid answer.
- code
class Solution:
def frequencySort(self, s: str) -> str:
res = []
for c, count in Counter(s).most_common():
res.append(c*count)
return "".join(res)
- code bucket sort
class Solution:
def frequencySort(self, s: str) -> str:
if not s: return s
# Determine the frequency of each character.
counts = collections.Counter(s)
max_freq = max(counts.values())
# Bucket sort the characters by frequency.
buckets = [[] for _ in range(max_freq + 1)]
for c, i in counts.items():
buckets[i].append(c)
# Build up the string.
string_builder = []
for i in range(len(buckets) - 1, 0, -1):
for c in buckets[i]:
string_builder.append(c * i)
return "".join(string_builder)