Sort Characters By Frequency
Problem Description
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.
Example 2:
Input: s = "cccaaa"
Output: "aaaccc"
Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.
Example 3:
Input: s = "Aabb"
Output: "bbAa"
Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.
Constraints:
- 1 <= s.length <= 5 * 105
sconsists of uppercase and lowercase English letters and digits.
Solve it on LeetCode
Approaches
1. Brute-force sorting
Intuition:
The simplest way to solve the problem is to count the frequency of each character and then sort the characters based on their frequency. This can be achieved using a hashmap to count frequencies and then converting it to a list or array for sorting.
Steps:
- Create a hashmap to store the frequency of each character.
- Convert the hashmap to a list of characters.
- Sort the list using a custom comparator based on frequency.
- Build the resulting string based on sorted order.
Code:
- Time Complexity: O(n log n) - due to sorting the characters.
- Space Complexity: O(n) - for storing the frequency map and the result.
2. Bucket Sort
Intuition:
To improve on the sorting time, we can use bucket sort which exploits the fact that frequency maximum is bounded by the string length. By placing characters into buckets indexed by frequency, we can directly build the string.
Steps:
- Count frequency of each character and find the maximum frequency.
- Create buckets where each index corresponds to characters that have that frequency.
- Fill the buckets with the corresponding characters.
- Traverse the buckets in reverse order to create the output string by frequency.
Code:
- Time Complexity: O(n) - counting the frequency and creating string, assuming bounded frequency.
- Space Complexity: O(n) - for storing the buckets and resulting string.
3. Using Priority Queue (Optimal)
Intuition:
We can also use a max-heap to always extract the most frequent element. This provides an efficient way to manage and prioritize elements by frequency without fully sorting the list of characters.
Steps:
- Count frequency of each character.
- Use a priority queue (max-heap) to store entries sorted by frequency.
- Extract characters from the priority queue and append to the result string.
Code:
- Time Complexity: O(n log k) - where n is the number of characters and k is the unique characters (k ≤ n).
- Space Complexity: O(n) - for the max-heap and the result string.