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.Problem Overview: Given a string s, reorder its characters so that characters with higher frequency appear first. If two characters have the same frequency, their relative order does not matter. The goal is to efficiently count occurrences and rebuild the string sorted by frequency.
Approach 1: HashMap + Sorting (O(n log k) time, O(n) space)
Count the frequency of every character using a HashMap. Once frequencies are known, convert the map entries into a list and sort them by frequency in descending order. After sorting, iterate through the pairs and append each character frequency times to the result string. The sorting step dominates the runtime with O(k log k), where k is the number of unique characters (at most n). This approach is simple and readable, making it a strong default when working with hash tables and sorting.
The key insight is separating the problem into two phases: counting and ordering. Counting is linear using a hash lookup per character, and sorting ensures the highest frequency characters appear first. Many implementations also replace sorting with a priority queue (max heap), which repeatedly extracts the highest-frequency character. That version has the same O(n log k) complexity but uses a heap instead of sorting.
Approach 2: Counting + Bucket Sort (O(n) time, O(n) space)
A faster approach avoids comparison-based sorting entirely. First compute character frequencies with a map or fixed-size array. Then create a bucket array where index i stores all characters that appear exactly i times. Because the maximum frequency is at most n, the bucket array size is n + 1. Iterate the buckets from highest frequency down to 1 and append each character i times to the result.
This works because frequencies are integers within a limited range. Instead of sorting characters by frequency, you directly place them into frequency-indexed buckets. Building the frequency map takes O(n), distributing characters into buckets takes O(k), and constructing the result string takes O(n). The entire process runs in linear time, which makes this the optimal solution for large inputs and a good demonstration of bucket sort principles.
Recommended for interviews: Start with the HashMap + sorting approach because it clearly shows the frequency-count pattern used in many string problems. After that, mention the bucket sort optimization. Interviewers typically expect candidates to recognize that sorting by frequency can be replaced with buckets for an O(n) solution.
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:
In this Python solution, the collections.Counter class is used to create a frequency map of the characters. We then sort the items of this map based on frequency and concatenate them to form the result string.
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.
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.In this Python solution, we first use a defaultdict to obtain the frequency table. After establishing frequency buckets, we build the result by iterating over frequencies in descending order.
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.
We use a hash table cnt to count the occurrences of each character in the string s. Then, we sort the key-value pairs in cnt in descending order by the number of occurrences. Finally, we concatenate the characters according to the sorted order.
The time complexity is O(n + k times log k), and the space complexity is O(n + k), where n is the length of the string s, and k is the number of distinct characters.
| Approach | Complexity |
|---|---|
| Using HashMap and Sorting | Time Complexity: O(n log n), where n is the length of the string due to sorting. |
| Using Counting Sort and Bucket Sort | Time Complexity: O(n), since we distribute the frequencies and read back them in linear time. |
| Hash Table + Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap + Sorting | O(n log k) | O(n) | General solution that is simple to implement and easy to explain in interviews |
| HashMap + Max Heap | O(n log k) | O(n) | Useful when repeatedly extracting highest frequency elements |
| Counting + Bucket Sort | O(n) | O(n) | Best performance when frequencies are bounded and linear-time solution is desired |
Sort Characters By Frequency | Leetcode #451 • Techdose • 61,828 views views
Watch 9 more video solutions →Practice Sort Characters By Frequency with our built-in code editor and test cases.
Practice on FleetCode