Sort Characters by Frequency: Heap or Buckets

This one is a Medium-rated classic reported from Amazon, Bloomberg, Zoom interviews: "Sort Characters by Frequency". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Top-K and Heaps pattern on sight. Part 6 of 11 in the Top-K and Heaps arc.

The Problem

Given a string, return it sorted by character frequency, descending; characters with equal counts may appear in any relative order. Unlike Top-K questions, every group is output — which changes which tool is optimal, and noticing that is the point.

Input:  s = "tree"
Output: "eert" (or "eetr")

Recognizing the Top-K and Heaps Pattern

When a problem asks for the k largest, smallest, closest, or most frequent — or for repeated access to an extreme while data changes — a heap gives O(log n) insertion and O(1) access to the extreme. The signature trick: keep a bounded heap of size k with the opposite polarity (a min-heap to track the k largest), evicting the root on overflow. Python's heapq is a min-heap; negate values for max behavior.

Full ordering by frequency, not selection of k — so the bounded-heap trick buys nothing. A max-heap over all distinct characters is the natural fit; counts bounded by the string length also admit bucket grouping at O(n). Choosing tools by what the output actually requires is the meta-skill here.

The Approach

Count. Push (−count, char) for each distinct character; pop in order, appending each character repeated count times. With at most 62 alphanumerics (or any fixed alphabet) the heap is effectively O(1) — the real cost is building the output.

''.join over accumulated pieces, never += in a loop — string concatenation in a loop is quadratic and is a known silent performance flag in Python screens.

Python Solution

import heapq
from collections import Counter


def frequency_sort(s: str) -> str:
    """Characters ordered by descending frequency."""
    counts = Counter(s)
    heap = [(-count, ch) for ch, count in counts.items()]
    heapq.heapify(heap)
    pieces: list[str] = []
    while heap:
        count, ch = heapq.heappop(heap)
        pieces.append(ch * (-count))
    return "".join(pieces)

Complexity

• Time: O(n + d log d) — counting is O(n); heap work is over d distinct characters
• Space: O(n) — counts and the output

Interview Tips and Follow-Ups

• Case sensitivity is specified ('A' differs from 'a') — restate it; assumed case-folding is a quiet correctness bug.
• counter.most_common() sorts for you — fine to use if you state it is O(d log d) under the hood; hiding behind stdlib without knowing costs is the anti-signal.
• Bridge question: this plus a max-heap with cooldown becomes Task Scheduler and Reorganize String — the next two posts. Frequency plus greedy is a mini-pattern.

If this clicked, continue the Top-K and Heaps arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.