Sort Characters By Frequency
Problem
Given a string s, return a string where the characters are sorted in descending order based on their frequency of occurrence.
- 1 ≤ s.length ≤ 5 * 10⁵
- s consists of ASCII characters.
Example
s = "tree""eert"The character 'e' appears twice, while 't' and 'r' appear once each. Sorting by frequency places 'e' first, resulting in "eert" or "eetr". The algorithm counts frequencies using a hash map, then sorts characters by their counts in descending order. It then reconstructs the string by repeating each character according to its frequency.
Approach
Straightforward Solution
A naive approach would repeatedly scan the string to count frequencies for each character, resulting in O(n^2) time complexity, which is inefficient for large inputs.
Core Observation
The problem requires grouping characters by frequency and then ordering these groups from highest to lowest frequency. The fundamental truth is that frequency counting is naturally suited to hash maps, which provide O(1) average-time insertion and lookup.
Path to Optimal
The key recognition signals are 'frequency of characters', 'sort by frequency', and 'return string sorted by frequency'. These indicate the Hash Maps pattern because counting frequencies requires a data structure with fast insertion and lookup. After counting, sorting the frequency map entries by their counts in descending order allows reconstruction of the output string efficiently.
Optimal Approach
Use a hash map to count the frequency of each character in a single pass over the string. Then, sort the map entries by frequency in descending order. Finally, build the result string by repeating each character according to its frequency. This approach achieves O(n log k) time complexity, where k is the number of unique characters, and O(k) space complexity.
Time
O(n log k)
Counting frequencies takes O(n) time, where n is the length of the string. Sorting the frequency map entries takes O(k log k), where k is the number of unique characters. Since k ≤ n, the overall complexity is O(n log k).
Space
O(k)
The hash map stores frequencies for each unique character, requiring O(k) auxiliary space, where k is the number of unique characters in the string.
Pattern Spotlight
Hash Maps (Frequency Counting and Sorting)
When a problem requires grouping elements by frequency and then ordering them, use a hash map to count frequencies followed by sorting the entries by their counts to efficiently reconstruct the desired output.
Solution
| 1 | class Solution: |
| 2 | def frequencySort(self, s: str) -> str: |
| 3 | |
| 4 | freq = {} |
| 5 | |
| 6 | for ch in s: |
| 7 | freq[ch] = freq.get(ch, 0) + 1 |
| 8 | |
| 9 | result = [] |
| 10 | |
| 11 | for ch, count in sorted(freq.items(), key=lambda x: x[1], reverse=True): |
| 12 | result.append(ch * count) |
| 13 | |
| 14 | return "".join(result) |
Step-by-Step Solution
Count Frequencies of Each Character Using a Hash Map
| 4 | freq = {} |
| 6 | for ch in s: |
| 7 | freq[ch] = freq.get(ch, 0) + 1 |
Objective
To build a frequency map that records how many times each character appears in the input string.
Key Insight
A hash map provides O(1) average-time insertion and lookup, making it ideal for counting frequencies in a single pass. By incrementing the count for each character as it is encountered, the algorithm efficiently aggregates frequency data without redundant scans.
Interview Quick-Check
Core Logic
Use a hash map to count occurrences of each character in one pass, enabling efficient frequency aggregation.
Common Pitfalls & Bugs
Forgetting to initialize counts or using a data structure with slower lookups (like a list for all ASCII chars) can degrade performance.
Sort Characters by Frequency in Descending Order
| 11 | for ch, count in sorted(freq.items(), key=lambda x: x[1], reverse=True): |
Objective
To order the characters based on their frequency counts from highest to lowest.
Key Insight
Sorting the frequency map entries by their counts ensures that characters with the highest frequency appear first in the output. Using a custom key function in sorting allows direct comparison of frequency values, enabling an efficient and clear sorting step.
Interview Quick-Check
Core Logic
Sort the frequency map items by their counts in descending order to prepare for output reconstruction.
Common Pitfalls & Bugs
Sorting in ascending order or forgetting to reverse the sort leads to incorrect output ordering.
Build the Result String by Repeating Characters According to Frequency
| 9 | result = [] |
| 12 | result.append(ch * count) |
| 14 | return "".join(result) |
Objective
To construct the final output string by concatenating each character repeated by its frequency count.
Key Insight
Repeating each character by its frequency and appending to a list avoids inefficient string concatenations. Joining the list at the end produces the final string efficiently. This approach leverages Python's string multiplication and join operations for optimal performance.
Interview Quick-Check
Core Logic
Repeat each character by its frequency and append to a list, then join all parts to form the final string.
Common Pitfalls & Bugs
Using string concatenation in a loop instead of list append and join can cause quadratic time complexity.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
for ch, count in sorted(freq.items(), key=lambda x: x[1], reverse=True):Sort the frequency dictionary items by frequency in descending order.
Sorting by frequency ensures that characters with higher counts appear first in the output, which is the core requirement of the problem.
freq[ch] = freq.get(ch, 0) + 1Increment the frequency count for the current character in the dictionary.
Using `get` with a default of 0 ensures that characters not yet seen are initialized properly, preventing key errors and enabling correct counting.
return "".join(result)Join all parts in the result list into a single string and return it.
Joining the list of repeated characters produces the final output string efficiently in O(n) time, where n is the length of the input string.
freq = {}Initialize an empty dictionary to store character frequencies.
This dictionary is the foundation for counting how many times each character appears, enabling O(1) average-time updates and lookups.
result.append(ch * count)Append the current character repeated by its frequency to the result list.
Repeating the character by its count and appending it to the list efficiently builds the output segments without repeated string concatenation overhead.
result = []Initialize an empty list to accumulate the output string parts.
Using a list to collect repeated characters avoids inefficient string concatenations, which would otherwise cause quadratic time complexity.
for ch in s:Iterate over each character in the input string.
This loop processes every character exactly once, ensuring the frequency count is accurate and complete.
Test Your Understanding
Why is sorting the frequency map entries by their counts necessary instead of just iterating over the map?
Because the problem requires the output string to be sorted in descending order of character frequency, sorting the frequency map entries ensures characters with higher frequency appear first, which cannot be guaranteed by iterating over the map in arbitrary order.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct Sort Characters By Frequency from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Sort Characters By Frequency drill