Sort Characters By Frequency

Sort Characters By Frequency

What is this problem about?

"Sort Characters By Frequency" is a string-based optimization problem. Given a string, you need to rearrange its characters such that they appear in decreasing order of their frequency. If multiple characters have the same frequency, their relative order doesn't matter.

For instance, in the string "tree", 'e' appears twice, while 't' and 'r' appear once. A valid output would be "eert" or "eetr". This problem combines counting, sorting, and string construction.

Why is this asked in interviews?

This is a popular medium-level question at companies like Microsoft, Amazon, and Bloomberg. it tests your ability to use Hash Tables for frequency counting and your choice of sorting strategy. It also introduces "Bucket Sort" as an alternative to standard $O(N \log N)$ sorting, which is a great way to show that you can optimize for specific constraints (since the maximum frequency is limited by the string length).

Algorithmic pattern used

There are two main approaches:

1. Max-Heap / Standard Sort: Count frequencies with a Hash Table, put the (char, freq) pairs into a list, and sort by freq in $O(N \log N)$ time.
2. Bucket Sort: Count frequencies. Create an array of buckets where bucket[i] stores all characters that appear i times. Iterate through the buckets from largest to smallest to build the result string in $O(N)$ time. This is faster when the number of unique characters is large but smaller than the string length.

Example explanation

Input: "banana"

1. Count: {'a': 3, 'n': 2, 'b': 1}
2. Buckets:
   • bucket[3] = ['a']
   • bucket[2] = ['n']
   • bucket[1] = ['b']
3. Build:
   • 3 'a's -> "aaa"
   • 2 'n's -> "aaann"
   • 1 'b' -> "aaannb" Result: "aaannb" (or "nnnaab" if order was different).

Common mistakes candidates make

A common mistake is forgetting that uppercase and lowercase characters are usually treated as different (e.g., 'A' and 'a'). Another error is inefficient string concatenation; in languages like Java or Python, you should use a StringBuilder or .join() to build the result in $O(N)$ time instead of repeatedly adding to a string ($O(N^2)$). Finally, some candidates fail to use the most efficient sorting method for the given constraints.

Interview preparation tip

For the "Sort Characters By Frequency interview question," always consider Bucket Sort first. Whenever the "values" you are sorting by are bounded (like frequency is bounded by the length of the string), Bucket Sort can often give you a linear time complexity, which will impress any interviewer.