← Non-Comparison Sorts (Counting, Radix, Bucket)

Sort Characters By Frequency

Medium
Solve it on LeetCode ↗

The problem

Rearrange a string so characters appear in decreasing order of frequency (ties in any order).

Stuck? Reveal hints one at a time

How to approach it

  1. 1Count each character’s occurrences.
  2. 2Create buckets indexed by frequency; drop each character into bucket[frequency].
  3. 3Walk buckets from n down to 1, appending each character repeated by its frequency.

Key insight

When the sort key is a small integer (frequency ≤ n), bucket indexing replaces comparison sorting — the same trick behind Top K Frequent Elements.

The solution

Watch out for

  • String concatenation in a loop is quadratic in some runtimes — collect parts and join.
  • Case-sensitive: "A" and "a" count separately.