Skip to main content
DSA patterns

Sort Characters By Frequency

mediumHeaps and top-K Must-doAmazonMicrosoftCognizant

Problem statement

You get a string s. Rearrange its characters so that whichever character appears most often comes first, then the next most frequent, and so on down to the least frequent — with every occurrence of a given character kept together as one block. If several characters are tied in frequency, any order between those tied groups is accepted, but characters must never be interleaved: every occurrence of the same character has to sit in one contiguous run.

Uppercase and lowercase versions of the same letter count as different characters ('A' and 'a' are tracked separately), and digits are treated the same way as letters — just another symbol to count and group.

Examples

Example 1

Input: s = "tree"

Output: "eert"

Explanation: 'e' appears twice, while 'r' and 't' each appear once, so 'e' must come first. "eetr" is also accepted, since the order between 'r' and 't' — the two tied, less-frequent characters — doesn't matter, as long as each is kept in one block.

Example 2

Input: s = "cccaaa"

Output: "aaaccc"

Explanation: 'c' and 'a' are tied at 3 occurrences each, so either "aaaccc" or "cccaaa" is valid. "cacaca" is rejected: even though it has the right counts, it splits the same character across separate runs instead of keeping each one together.

Example 3

Input: s = "Aabb"

Output: "bbAa"

Explanation: 'b' appears twice and must come first. 'A' and 'a' are different characters (capitalization matters) and both appear once, so either order between them is fine — "bbaA" is also accepted. "Aabb" is rejected because 'b' (the more frequent character) doesn't come first.

Hints

Hint 1: Start by counting how many times each character appears — a hash map from character to count is the natural first step no matter which approach you end up using.

Approach

Optimal: Bucket sort by frequency

Intuition

A character's frequency can never exceed n (the length of the whole string), so instead of sorting the distinct characters by frequency, "sort" them for free by using their frequency directly as an array index. Make an array of buckets, one slot per possible count from 0 to n. Drop each distinct character into buckets[its count]. Then walk the buckets from the highest possible count down to 1, and for every character found in a bucket, write it out that many times. Because the buckets are visited in a fixed, already-descending order, there's no comparison sorting step at all — this is what pushes the time down from the k log k of the better approach to a flat O(n).

Steps

  1. Count each character's frequency with a hash map.
  2. Create an array of n + 1 empty buckets, indexed by count (0 through n).
  3. For each distinct character, append it to buckets[its count].
  4. Walk cnt from n down to 1. For every character in buckets[cnt], append that character to the result cnt times.
  5. Return the built result.

Dry run

s = "tree" (n = 4)

step detail
counts {t: 1, r: 1, e: 2}
buckets after distributing buckets[1] = [t, r], buckets[2] = [e], all other buckets empty
walk cnt = 4, 3: both empty, nothing appended
walk cnt = 2: buckets[2] = [e] → append "e" × 2 → result so far: "ee"
walk cnt = 1: buckets[1] = [t, r] → append "t" × 1, then "r" × 1 → result: "eetr"

Final result: "eetr" — a valid answer (e first since it's most frequent, then t and r in either order since they're tied).

Edge cases: an empty bucket at a given count is simply skipped — the inner loop over buckets[cnt] does nothing when that count wasn't used by any character. A string where every character is unique (all counts equal to

  1. puts everything into a single bucket, buckets[1], and the walk from n down to 1 finds nothing until it reaches that one bucket.

Complexity

Time O(n) - no comparison sort at all. Counting is O(n), distributing distinct characters into buckets is O(k) (k ≤ 62), and building the output by walking the buckets is O(n), since the total number of characters written out across every bucket is exactly n.

Space O(n) - for the output, plus O(n) for the buckets array (indexed by every possible count from 0 to n, even though only a handful of slots are ever used).

from collections import Counter


class Solution:
    def frequencySort(self, s: str) -> str:
        counts = Counter(s)
        n = len(s)
        buckets = [[] for _ in range(n + 1)]  # buckets[c] = chars that appear exactly c times
        for ch, cnt in counts.items():
            buckets[cnt].append(ch)
        parts = []
        for cnt in range(n, 0, -1):
            for ch in buckets[cnt]:
                parts.append(ch * cnt)
        return "".join(parts)


if __name__ == "__main__":
    print(Solution().frequencySort("tree"))
    print(Solution().frequencySort("cccaaa"))
    print(Solution().frequencySort("Aabb"))
RecapThe whole problem in a few lines, for the night before
  • Spot it: reorder a string so the most frequent characters come first
  • Idea: count each character with a hash map, then sort by count (or use count buckets) and repeat each character that many times
  • Cost: O(n log k) time with a sort, O(n) with buckets; O(n) space
  • Trap: all copies of a character must stay together; 'a' and 'A' are different characters

Interview follow-ups

  • What if the string is too large to fit in memory, but you can stream through it once to count, and it's fine to do a second pass to build the output?

    The counting step already only needs one linear pass and produces a small map (at most 62 entries) regardless of how long the string is, so that part scales fine as a stream. Building the output does need a second pass over the (now-known) counts to write each character's block, but that second pass can also be streamed out — for example written directly to a file or a network socket in bucket order — instead of being held as one giant string in memory at once.

  • How would this change if you only needed the top 5 most frequent characters, not the fully sorted string?

    Skip the full sort or bucket walk once the top 5 are found — a fixed-size min-heap of size 5 (the same idea as the min-heap approach to Kth Largest Element in a Stream) lets you track only the 5 most frequent characters seen so far while scanning the count map once, in O(k log 5) instead of O(k log k) or a full O(n) bucket pass. This matters more as the alphabet size k grows (for example, if characters were arbitrary strings instead of single letters) — with a fixed 62-character alphabet the difference is negligible.

Frequently asked questions

The better and optimal approaches never sort individual character positions at all — they sort (or bucket) the small set of distinct characters, then write each one out as a whole block in one place. There's no way for two different characters to end up interleaved, because each one is only ever written once, as a complete run. The brute-force approach sorts every position in the original string directly, so if two different characters tie in frequency, a frequency-only key can't tell their positions apart — the tie-breaker is what forces same-character positions next to each other instead of leaving them wherever they started.

No — the checker only requires that (1) every character appears the correct number of times, (2) each character's occurrences are all contiguous, and (3) blocks are ordered from highest frequency to lowest. Whether 'a' comes before 'c' or 'c' comes before 'a' when they're tied at the same count is entirely up to the algorithm; nothing about hash map iteration order or bucket insertion order needs to be controlled for.

The buckets array is indexed by count, not by character — and a character's count can be as large as n itself (an entire string of one repeated character), so the array needs n + 1 slots to have room for every possible count value, even though only a handful of those slots ever end up holding anything. This is the classic space-for-time trade of a counting/bucket sort: it spends O(n) memory on mostly-empty buckets in exchange for avoiding any comparison sorting at all.

Ranking things by how often they occur — the most frequent error codes in a log window, the busiest endpoints in a traffic sample, the most-repeated alert type in an incident — is exactly this pattern: count occurrences, then present them ordered from most common to least, grouped rather than scattered.