Sort Characters By Frequency
Medium · Arrays & Hashing · Hash Table · String · Sorting · Bucket Sort · Counting
Problem
Given a string s, reorder its characters so that they appear in decreasing order of frequency: a character that occurs more often comes before one that occurs less often.
All copies of the same character must be grouped together. Return the reordered string. When several characters share a frequency, they may appear in any order, and every such answer is accepted.
Uppercase and lowercase letters are different characters.
Examples
Input: s = "letter" Output: "eettlr"
"e" and "t" appear twice and come first; "l" and "r" appear once. "tteerl" or "eettrl" would also be accepted.
Input: s = "Aaa" Output: "aaA"
"a" occurs twice and "A" once: case matters.
Input: s = "loopool" Output: "oooollp"
Four o, two l, one p. Every frequency is different, so this is the only answer.
Constraints
- 1 <= len(s) <= 5 · 10^5
- s consists of uppercase and lowercase English letters and digits
Approaches
- Count, then sort the distinct characters — time O(n + k log k), space O(n)
Follow-up
If ties must come out in a fixed order (for example alphabetical), the answer becomes unique: sort each bucket, or break ties by character in the comparison. How does that change the cost?
Related problems
Start free on Cariara · Coding problems · System design studio
