Sort characters by fill frequency

Question

Given a string of fill codes, rearrange its characters so the most frequent character comes first (repeated as many times as it occurs), then the next most frequent, and so on. Break ties alphabetically.

fills = "tree"
-> "eert"          # e appears twice, then r, t alphabetically

Return the frequency-sorted string. Aim for $O(n + u \log u)$ .

Accepted Answer

Count each character, then order the distinct characters by a compound key: descending count, then the character itself for tie-breaking. Rebuild the string by repeating each character by its count in that order. Tracing "tree": counts are t: 1, r: 1, e: 2. Sorting puts e first (count 2), then r and t alphabetically, producing "eert". Time O(n + u \log u) for u distinct characters, space O(n) for the rebuilt string. The alphabetical tie-break makes the output deterministic; drop it if any order among equal-frequency characters is acceptable. Takeaway. Count, sort by a compound key, then expan…

Sort characters by fill frequency

Your answer

More Coding questions