Character Frequency + Sorting

Before we start

You have seen frequency maps in Chapter 2 (Hashing). This chapter shows what happens after you build the map — when the goal isn't "find" but "rearrange." By the end you will be able to:

• Sort characters by how often they appear, most frequent first.
• Decide when a bucket sort is better than a heap for this family.
• Recognise the "reorganise so no two adjacent are the same" variant and know exactly when it is impossible.

Read the story first. The code will make immediate sense once you have the picture.

Picture this first (no code yet)

The actual problem

Sort Characters By Frequency (LC #451):

Given string s, return it rearranged so that characters appear in descending order of frequency.

Input:  "tree"
Output: "eert"   (or "eetr") — 'e' appears twice, 't' and 'r' once each

The naive approach would sort all characters directly — O(n log n). But we don't need character-level sorting at all. We only need to sort the frequency counts, of which there are at most 26 (for lowercase letters). That is the key efficiency insight.

First, the slow way (so you feel the pain)

Sort every character individually:

def sortByFrequency_slow(s: str) -> str:
    return "".join(sorted(s, key=lambda c: -s.count(c)))

For each character in the sorted call, s.count(c) scans the entire string — O(n) per character, O(n) total characters → O(n²) just for the keys. For n = 100 000 that is 10 billion operations. For a 26-character alphabet, we can do this in a single O(n) pass.

The turning point

The one idea to remember

Watch it happen, frame by frame

Input: "treeeeat"

Step 1 — Build frequency map:
  t → 1
  r → 1
  e → 4
  a → 1

Step 2 — Sort by frequency descending:
  [('e', 4), ('t', 1), ('r', 1), ('a', 1)]
  (ties broken arbitrarily — any order is valid)

Step 3 — Write output:
  'e' × 4 → "eeee"
  't' × 1 → "eeeeet"   ← wrong, I mean append 't'
  'r' × 1 → "eeeetr"
  'a' × 1 → "eeeeetra"

Output: "eeeetra"  ✅  (or any permutation of single-occurrence chars at the end)

The code, line by line

from collections import Counter
import heapq

def frequencySort(s: str) -> str:
    freq = Counter(s)                          # {'e':4, 't':1, 'r':1, 'a':1}

    # max-heap: Python has min-heap, so negate count
    heap = [(-count, char) for char, count in freq.items()]
    heapq.heapify(heap)                        # O(k) where k = distinct chars

    result = []
    while heap:
        neg_count, char = heapq.heappop(heap)  # most frequent first
        result.append(char * (-neg_count))     # repeat char by its count

    return "".join(result)

• Counter(s) — one pass, O(n), builds {char: count}.
• Negate counts for max-heap simulation — Python's heapq is a min-heap; negating turns smallest-negative (= largest count) into the highest priority.
• char * (-neg_count) — Python string multiplication. 'e' * 4 = "eeee". One line, no loop.
• "".join(result) — assembles the final string in O(n).

Alternative: bucket sort (O(n), no heap)

If you want O(n) strict (no log factor), use bucket sort: index by frequency.

def frequencySort_bucket(s: str) -> str:
    freq  = Counter(s)
    n     = len(s)
    # buckets[i] = list of chars that appear exactly i times
    buckets = [[] for _ in range(n + 1)]
    for char, count in freq.items():
        buckets[count].append(char)

    result = []
    for count in range(n, 0, -1):      # highest frequency first
        for char in buckets[count]:
            result.append(char * count)

    return "".join(result)

No sorting, no heap — just array indexing. O(n) total.

Variant: Reorganize String (LC #767)

Problem: rearrange characters so no two adjacent characters are the same. Return "" if impossible.

When is it impossible? If any character appears more than (n + 1) // 2 times, it cannot be spaced out — it must occupy more than half the positions, forcing two copies to be adjacent.

n = 5  →  max allowed = 3  (positions 0, 2, 4 for the dominant char)
"aaab" → 'a' appears 3 times, n=4, max = 2 → impossible → return ""
"aab"  → 'a' appears 2 times, n=3, max = 2 → possible → "aba"

Greedy strategy: always place the most frequent remaining character next (as long as it isn't the same as the last character placed). Use a max-heap to always access the most frequent.

def reorganizeString(s: str) -> str:
    freq = Counter(s)
    n    = len(s)

    # Impossibility check
    if max(freq.values()) > (n + 1) // 2:
        return ""

    heap = [(-count, char) for char, count in freq.items()]
    heapq.heapify(heap)

    result = []
    prev_count, prev_char = 0, ""   # last placed character (don't repeat it)

    while heap:
        count, char = heapq.heappop(heap)   # most frequent available

        result.append(char)
        count += 1                           # count is negative; += 1 means one fewer

        # re-add previous character now that it's no longer "last placed"
        if prev_count < 0:
            heapq.heappush(heap, (prev_count, prev_char))

        prev_count, prev_char = count, char

    return "".join(result)

Frame-by-frame: "aab"

freq = {'a': 2, 'b': 1}   heap = [(-2,'a'), (-1,'b')]

Step 1: pop (-2,'a'). Place 'a'. count=-1. prev=(−1,'a').
        heap = [(-1,'b')]
        result = ['a']

Step 2: pop (-1,'b'). Place 'b'. count=0.
        Re-add prev (-1,'a') → heap = [(-1,'a')]
        prev=(0,'b').
        result = ['a','b']

Step 3: pop (-1,'a'). Place 'a'. count=0.
        Re-add prev (0,'b') → count==0, don't re-add.
        result = ['a','b','a']

Output: "aba"  ✅

Heap vs bucket sort — when to use which

Where to spot this pattern

Trigger words:

• "sort by frequency" or "most frequent first"
• "rearrange so no two adjacent are the same"
• "reorganize" + any constraint involving character repetition
• "top K frequent characters" (frequency map + heap from Chapter 9.2)

5 disguises:

1. Sort Characters By Frequency (LC #451): bucket sort or heap, output sorted by count.
2. Reorganize String (LC #767): greedy max-heap, always place most frequent non-adjacent.
3. Task Scheduler (LC #621): same greedy as reorganize but with cooldown period k; count idle slots.
4. Rearrange String k Distance Apart (LC #358): reorganize with gap k instead of gap 1.
5. Largest Number (LC #179): custom comparator sort — "which concatenation is bigger?" Not character frequency, but the same "sort by a derived key" skeleton.

Common traps

Complexity

k = number of distinct characters (≤ 26 for lowercase).

Say it like a pro (interview one-liner)

"I'll build a frequency map in O(n), then use a max-heap to always place the most frequent remaining character — skipping it if it's the same as the last placed. For 'sort by frequency' without constraints I'd use bucket sort for strict O(n). Reorganize String adds the adjacent constraint, so I need the heap's O(log k) ordering at every step."

freq = Counter(s)
buckets = [[] for _ in range(len(s) + 1)]
for char, count in freq.items():
    buckets[count].append(char)
result = []
for i in range(len(s), 0, -1):
    for c in buckets[i]: result.append(c * i)

if max(freq.values()) > (n+1)//2: return ""   # impossibility check first
heap = [(-cnt, c) for c, cnt in freq.items()]; heapq.heapify(heap)
# pop most frequent, place it, re-add previous char

Check yourself

Practice problems

Next up: Parentheses Problems — when a stack (or a simple counter) turns bracket-matching and longest-valid-sequence problems into clean O(n) solutions.