Watch 10 video solutions for Sort Characters By Frequency, a medium level problem involving Hash Table, String, Sorting. This walkthrough by Techdose has 61,828 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |