451. Sort Characters By Frequency

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)