Sort Characters by Frequency

Given a string, return it sorted so characters appear in decreasing order of frequency. Equal-frequency characters may be ordered any way. So "tree" can answer "eert" or "eetr" — 'e' appears twice, 't' and 'r' once each.

The key insight: the output is built per character, not per position. The machine first counts every character in one pass, then ranks the distinct characters by count. A max-heap over (count, char) pairs emits characters in descending frequency with a simple pop loop; each pop appends the character count times.

Approach in steps:

1. Count frequencies with a hash map: O(n).
2. Push every (count, char) into a max-heap.
3. Pop the most frequent, append it count times, repeat until the heap is empty.

import heapq
from collections import Counter
 
def frequencySort(s):
    counts = Counter(s)
    heap = [(-c, ch) for ch, c in counts.items()]
    heapq.heapify(heap)
    out = []
    while heap:
        c, ch = heapq.heappop(heap)
        out.append(ch * (-c))
    return "".join(out)

Time is O(n + k log k) for k distinct characters; space is O(n) for the output and counter. When k is small relative to n, this is effectively linear.

Trickiest edge case: ties in frequency. The problem accepts any order for equal counts, so the heap does not need a deterministic tie-break — but be careful if you later add one, because mixing count and character into the tuple changes what Python compares first. Also, all-same-character input like "aa" must yield "aa", not a single "a" — the multiplication step repeats the character exactly count times.