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 * 105s consists of uppercase and lowercase English letters and digits.In #451 Sort Characters By Frequency, the goal is to rearrange characters in a string so that characters with higher frequencies appear first. A common strategy is to first count the frequency of each character using a hash map. Once the counts are known, the next step is to organize characters based on their frequencies.
One efficient method uses a max heap (priority queue) where characters are pushed with their frequencies, allowing the most frequent characters to be extracted first. Another optimized technique is bucket sort, where characters are grouped into buckets indexed by frequency. Since the maximum frequency is bounded by the string length, this approach can be very efficient.
After grouping or ordering by frequency, construct the result string by repeating each character according to its count. These strategies typically run in O(n log k) time using a heap or O(n) with bucket sorting, where n is the string length and k is the number of unique characters.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map + Max Heap | O(n log k) | O(k) |
| Hash Map + Bucket Sort | O(n) | O(n) |
Techdose
This approach involves using a hash map to count the frequency of each character, followed by sorting the characters by frequency in descending order. Here's how the approach works step-by-step:
Time Complexity: O(n log n), where n is the length of the string due to sorting.
Space Complexity: O(n), for the frequency map storage.
1function frequencySort(s) {
2 const freqMap = {};
3 for (const char of s) {
4In JavaScript, we use an object to track frequencies, sort them by frequency with Object.entries(), and use map() and join() to form the string.
This approach leverages the Bucket Sort technique where we'll map frequencies to characters directly. This is especially efficient when the range of possible frequencies is low compared to the number of characters.
i stores characters appearing i times.Time Complexity: O(n), since we distribute the frequencies and read back them in linear time.
Space Complexity: O(n), for the result string and bucket storage.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, it can be solved using bucket sort. By placing characters into buckets based on their frequency, you can build the result in descending frequency order without needing a priority queue.
Yes, variations of frequency-based string problems are common in technical interviews, including FAANG companies. They test understanding of hash maps, heaps, and efficient string manipulation techniques.
A hash map is essential for counting character frequencies efficiently. After counting, either a priority queue (max heap) or bucket array is typically used to sort characters by their frequency.
A common optimal approach is to count character frequencies using a hash map and then organize them using bucket sort or a max heap. Bucket sort can achieve linear time in many cases because the frequency range is limited by the string length.
The solution uses a frequency map and an array of lists to accumulate characters based on frequency, constructing the result efficiently by iterating from high to low frequency indices.