Sort Characters By Frequency
Understanding the Problem
We need to rearrange the characters in a string so that the most frequent characters come first. Characters with the same frequency can appear in any order relative to each other, but all occurrences of the same character must be grouped together. So "aaabb" is valid for a string where 'a' appears 3 times and 'b' appears 2 times, but "ababa" is not.
Three details shape the solution. The problem is case-sensitive, so 'A' and 'a' are different characters. Digits are also valid characters in the input. And when two characters have the same frequency, any ordering between them is acceptable, which means we do not need a stable sort or any tiebreaking logic.
The task reduces to two steps: count how often each character appears, then build a result string by outputting characters from most frequent to least frequent.
Key Constraints:
1 <= s.length <= 5 * 10^5→ With up to 500,000 characters, we need O(n log n) or better. An O(n^2) approach would risk timing out.sconsists of uppercase and lowercase English letters and digits → At most 62 distinct characters (26 + 26 + 10). The alphabet is small and fixed, so ordering the distinct characters is cheap no matter how long the string is.
Approach 1: Sorting
Intuition
Count how many times each character appears, sort the distinct characters by their frequency in descending order, then build the result by repeating each character the appropriate number of times.
The alphabet has at most 62 distinct characters, so the sort runs over at most 62 entries regardless of how long the string is. The dominant work is counting and string building, both O(n). Sorting a fixed-size set of entries does not change that.
Algorithm
- Build a frequency map that counts how many times each character appears in the string.
- Collect the entries of the frequency map (each entry is a character-count pair).
- Sort these entries by count in descending order.
- Build the result string by appending each character repeated by its count.
Example Walkthrough
Code
- Time Complexity: O(n + k log k), where n is the length of the string and k is the number of distinct characters. Counting frequencies takes O(n). Sorting k distinct characters takes O(k log k). Building the result takes O(n). Since k is at most 62, this is effectively O(n).
- Space Complexity: O(n + k). The frequency map uses O(k) space. The result string uses O(n).
A max-heap is another way to pull characters out in frequency order, extracting the most frequent remaining character one at a time.
Approach 2: Max-Heap (Priority Queue)
Intuition
Instead of sorting all entries at once, use a max-heap (priority queue) to extract the character with the highest frequency. Count the frequencies first, push all character-frequency pairs into a max-heap ordered by frequency, then repeatedly extract the maximum and append that character to the result.
The heap returns the most frequent remaining character in O(log k) time per extraction, with at most 62 distinct characters in play. This structure also generalizes to a partial request like "give me only the top 3 most frequent characters," where you would extract three times and stop instead of draining the whole heap.
Algorithm
- Build a frequency map counting each character's occurrences.
- Push every (frequency, character) pair into a max-heap.
- While the heap is not empty:
- Extract the pair with the highest frequency.
- Append that character repeated by its frequency to the result.
- Return the result string.
Example Walkthrough
Code
- Time Complexity: O(n + k log k), where n is the length of the string and k is the number of distinct characters. Counting takes O(n). Building and extracting from the heap takes O(k log k). Building the result takes O(n). With k at most 62, this is effectively O(n).
- Space Complexity: O(n + k). The frequency map and heap together use O(k) space. The result string uses O(n).
Both approaches order the distinct characters by comparison, either through a sort or a heap. Because every frequency is an integer between 1 and n, bucket sort can order them without any comparisons and reach a true O(n) solution.
Approach 3: Bucket Sort (Optimal)
Intuition
The maximum possible frequency of any character is n, the length of the string. So we can create an array of n+1 buckets, where bucket[i] holds all characters that appear exactly i times. After populating the buckets, we walk from bucket[n] down to bucket[1], appending each character the appropriate number of times. The descending walk replaces the sort or heap with plain array indexing.
This is bucket sort applied to a bounded integer key. Frequencies range from 1 to n, at most 62 distinct characters are spread across those buckets, and the whole process is O(n).
The outer loop visits n+1 bucket indices, most of them empty, which contributes O(n). The inner work appends each character freq times, and the frequencies of all distinct characters sum to exactly n, since every character in the input lands in exactly one bucket. So the appends total O(n) across the entire run, not O(n) per bucket. The two parts add to O(n).
Algorithm
- Build a frequency map counting each character's occurrences.
- Create an array of buckets with size n+1 (where n is the string length). Each bucket is a list of characters.
- For each character in the frequency map, place it into the bucket at index equal to its frequency.
- Iterate through the buckets from index n down to 1. For each character in the current bucket, append it repeated by the bucket index (which is its frequency) to the result.
- Return the result string.
Example Walkthrough
Code
- Time Complexity: O(n). Counting frequencies takes O(n). Creating and populating buckets takes O(k), where k is the number of distinct characters. Walking the buckets and building the result takes O(n) total. Since k is at most 62, the overall complexity is O(n).
- Space Complexity: O(n + k). The bucket array has n+1 slots. The frequency map uses O(k). The result string uses O(n).