Skip to main content

451. Sort Characters By Frequency

medium

Sort a string's characters by how often they appear, ties broken any way. A staple top-k variant — the heap version is the most readable approach.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • 1 <= s.length <= 5 * 10^5
  • s consists of uppercase and lowercase English letters and digits.

Examples

Example 1

Input
s = "tree"
Output
"eert"

Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. 'eetr' is also a valid answer.

Example 2

Input
s = "cccaaa"
Output
"aaaccc"

Explanation: Both 'c' and 'a' appear three times, so 'aaaccc' is also a valid answer.

Example 3

Input
s = "Aabb"
Output
"bbAa"

Explanation: 'b' appears twice; 'A' and 'a' each appear once. 'A' and 'a' are different cases. 'bbaA' is also valid.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Count character frequencies with a hash map.

Hint 2

Push (count, char) pairs into a max-heap. Pop and emit count copies of each character until empty.

Hint 3

Alternative: bucket sort by count. Index i holds all chars with frequency i. Walk buckets high-to-low. O(n) time, no heap.

Hint 4

Both are fine answers. Heap is more idiomatic; bucket sort is asymptotically faster for very large alphabets.

Solution approach

Reveal approach

Count character frequencies in a hash map in O(n). Then build a max-heap of (count, char) pairs in O(k log k) where k is the distinct-char count. Pop the heap; for each (count, char) emit count copies of char and append to a result buffer. Join at the end. Total O(n + k log k). For ASCII inputs k <= 62 so the log factor is negligible — but on Unicode inputs the alphabet could be 10^4+ and the analysis matters. Bucket-sort alternative: allocate buckets indexed 0..n, drop each char into bucket [count[char]], then walk buckets from n down to 1 and emit. O(n) time, O(n) space. Use bucket sort when k is large or you want to drop the log factor.

Complexity

Time
O(n + k log k)
Space
O(n)

Related patterns

  • heap
  • top-k-elements
  • hash-map
  • bucket-sort

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft
  • Bloomberg

More Heaps practice problems

See all Heaps problems →