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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Sort Characters By Frequency and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →