< Back





451. Sort Characters By Frequency

Pretty fun question. Our first intuition, at least for interviews, is to use the Counter class from
the collections package to count the frequency of each character in the string. Then we can use the
most_common() method of the class to sort the characters in decreasing order by frequency. Finally,
we construct the string by iterating through each character and its frequency in decreasing order,
multiplying the character by its count, and appending it to a list. Then we use the "".join() method
to create the final string. This achieves a runtime of O(nlogn) because of the sorting step.

We can achieve O(n) time by using bucket sort. See, the order of the characters doesn't matter if
they're the same frequency. So we just need to sort the characters into different buckets based on
how often they're seen. We use a dictionary to index into a list in O(1) time, and this list contains
the characters that are seen at the particular frequency we're indexing into.

To create the final answer, we walk backwards through the dictionary starting at the max frequency.
The max frequency can be obtained in O(n) time, so this isn't an issue. As we walk backwards through
the buckets, we iterate through the list of characters in the bucket and append the multiplication
of the character with its frequency (the one derived from the bucket).

Finally, we join the list of characters with "".join() to return the answer.

The solution is as follows:


  from collections import Counter, defaultdict

  class Solution:
      def frequencySort(self, s: str) -> str:
          if not s: return s
          counts = Counter(s)
          max_freq = max(counts.values())

          buckets = defaultdict(list)
          for char, count in counts.items():
              buckets[count] += [char]

          ans = [
              char * count
              for count in range(max_freq, 0, -1)
              for char in buckets[count]
          ]

          return "".join(ans)


_ Time Complexity:

  O(n) - We count the occurrence of characters and find the max frequency - operations that take
  O(n) time.

_ Space Complexity:

  O(n) - We bucket sort and store the occurrences of the characters.