Sort Characters By Frequency

Intuition

Only counts matter, so tally each character first. Because a character can appear at most len(s) times, we can bucket by count: bucket[f] lists the characters that occur exactly f times. Walking buckets from the highest count down and emitting each character repeated f times produces a string sorted by decreasing frequency in linear time. This avoids the log factor of comparison sorting or a heap while still allowing arbitrary order among ties.

Algorithm walkthrough

1. 1Count the occurrences of each character with a hash map or a fixed-size array.
2. 2Build buckets indexed by frequency; append each character to bucket[its count].
3. 3Iterate frequencies from the largest down to 1.
4. 4For every character in the current bucket, append that character repeated frequency times to the output.
5. 5Join the pieces and return the resulting string.

Implementation

from collections import Counter


class Solution:
    def frequencySort(self, s: str) -> str:
        counts = Counter(s)
        buckets: list[list[str]] = [[] for _ in range(len(s) + 1)]
        for char, freq in counts.items():
            buckets[freq].append(char)
        pieces: list[str] = []
        for freq in range(len(s), 0, -1):
            for char in buckets[freq]:
                pieces.append(char * freq)
        return "".join(pieces)