Order Letters by Frequency
MediumArrays & Hashing
Problem
A typography tool wants to show which characters dominate a piece of text by rewriting it with the most frequent characters first.
Given s, return a string with the same characters, grouped so that all copies of a character are adjacent, with groups ordered by frequency descending. Characters with equal frequency are ordered by their character code, ascending (so digits before uppercase before lowercase).
Example 1
- Input:
- s = "banana"
- Output:
- "aaannb"
a appears 3 times, n twice, b once.
Example 2
- Input:
- s = "Aabb"
- Output:
- "bbAa"
b leads with 2; A and a tie at 1, and 'A' (65) comes before 'a' (97).
Constraints
- 1 ≤ s.length ≤ 5·10^5
- s contains English letters and digits.
Hint
Show the first hint
First find how often each character occurs.
Walkthrough
How to approach it
01Clarify before coding
- How are ties broken? By ascending character code, which makes the output unique.
- Are upper and lower case distinct? Yes, 'A' and 'a' are different characters.
- Which characters can appear? Letters and digits, so at most 62 distinct ones.
02Brute force
Sort the characters of s with a comparator using (frequency descending, character ascending), recounting frequencies in the comparator.
Cost: O(n² log n) if frequencies are recomputed per comparison; O(n log n) with a precomputed count. Both sort n characters when only the distinct ones need ordering.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.