Sort Characters By Frequency

Q: Is a heap a good alternative?

Yes: push (count, character) pairs into a max-heap and pop them in order. It costs O(n + m log m), where m is the number of distinct characters. That is close to linear when m is small, but buckets avoid the log factor entirely.

Q: Why is this on an infra-focused sheet?

It is the classic sort | uniq -c | sort -rn pipeline in code: count occurrences, then order by count. The bucket idea is useful whenever the values you sort by have a small, known range, such as HTTP status codes or retry counts.

mediumHeaps and top-K

Given a string s, rearrange its characters so that the most frequent character comes first, then the next most frequent, and so on. All copies of a character must be next to each other. Letters are case-sensitive, so A and a are different characters, and digits count too.

When two characters appear equally often, either may come first. Any arrangement that follows these rules is accepted.

Examples

Example 1

Input: s = "banana"

Output: "aaannb"

Explanation: a appears 3 times, n twice and b once. This is the only valid answer, since the counts are all different.

Example 2

Input: s = "Aabb"

Output: "bbAa"

Explanation: b appears twice. A and a appear once each and are different characters, so "bbaA" is also correct.

Hints

Approach

Count, then bucket sort by frequency.

Count each character.
Make len(s) + 1 buckets, where bucket f holds the characters that appear exactly f times.
Walk the buckets from len(s) down to 1, and for each character in a bucket, append it f times.

No comparisons between characters are needed, and each character of the output is written once, so the whole thing is linear.

ComplexityTime O(n)Space O(n)

Python

from collections import Counter
 
class Solution:
    def frequencySort(self, s: str) -> str:
        counts = Counter(s)
        buckets = [[] for _ in range(len(s) + 1)]   # index = frequency
        for ch, freq in counts.items():
            buckets[freq].append(ch)
        parts = []
        for freq in range(len(s), 0, -1):            # highest frequency first
            for ch in buckets[freq]:
                parts.append(ch * freq)
        return "".join(parts)

Follow-up questions

Break ties by the order in which characters first appear in the string.
Rearrange the string so that no two equal characters are adjacent, if possible (Reorganize String).

Frequently asked questions

Yes: push (count, character) pairs into a max-heap and pop them in order. It costs O(n + m log m), where m is the number of distinct characters. That is close to linear when m is small, but buckets avoid the log factor entirely.

Sorting by count alone treats all characters with equal counts as equal, and the sort is then free to leave them interleaved, like abab. Adding the character as a tie-breaker keeps each group together.

It is the classic sort | uniq -c | sort -rn pipeline in code: count occurrences, then order by count. The bucket idea is useful whenever the values you sort by have a small, known range, such as HTTP status codes or retry counts.

Problem statement