Coding Interview PatternsSort Characters By Frequency
MediumTop K Elements
Sort Characters By Frequency
Explanation & Solution
Description
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.
Input: s = "tree"
Output: "eert"
Explanation: 'e' appears twice while 'r' and 't' each appear once. So 'e' must appear before both 'r' and 't'. "eetr" is also a valid answer.
Constraints
1 <= s.length <= 5 * 10⁵sconsists of uppercase and lowercase English letters and digits.
Approach
Top K Elements pattern
1. Count Character Frequencies
- Iterate through the string and build a frequency map where each key is a character and each value is how many times it appears.
2. Create Buckets by Frequency
- Create an array of buckets where the index represents a frequency count (from 0 to
s.length). - Place each character into the bucket corresponding to its frequency.
- This avoids comparison-based sorting and achieves O(n) time.
3. Build Result from Highest Frequency
- Iterate through the buckets from highest index to lowest.
- For each non-empty bucket, sort the characters (to ensure deterministic output for same-frequency characters), then append each character repeated by its frequency count to the result string.
4. Return the Result
- The built string contains all characters sorted by decreasing frequency, with ties broken by character code order.
Key Insight
Bucket sort lets us avoid an O(n log n) comparison sort. Since frequencies range from 1 to n, we use the frequency as a direct index into an array of buckets. This gives us O(n) time complexity and O(n) space complexity, where n is the length of the string.
Visualization
Input:
[t, r, e, e]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps