451. Sort Characters By Frequency

Reference: LeetCode
Difficulty: Medium

Problem

Given a string, sort it in decreasing order based on the frequency of characters.

Example:

Analysis

HashMap + Sorting

• Build the map to count frequency.
• Build an array list to sort elements by frequency.
• Build the string.

Note: Actually you can also use PriorityQueue to sort.

Time: $O(N\log{M})$ where $M$ is the number of distinct characters.
Space: $O(N)$

• $O(M)$ the array and the map (with greater overhead).
• $O(N)$ the output string.

Using TreeSet here is not a good idea!

The code will not give correct results. In the tree example, r will be missing. It is because equals and compareTo methods should be consistent. Since we have a comparator (n1, n2) - > (map.get(n2)- map.get(n1)), when t and r have the same count, they are treated as the “same” characters in the set. Thus, t won’t be added into the set.

Bucket Sort

We can use n buckets to store characters with specific frequencies. It is a typical way to use much space to gain running time improvement.

Note:

Time: $O(N)$
Space: $O(N)$

• $O(M)$ the buckets and the map (with greater overhead).
• $O(N)$ the output string.

Comment
Junhao Wang
a software engineering cat