MediumHash TableStringSortingHeap (Priority Queue)Bucket SortCounting

Sort Characters By Frequency

1 approach, code in every language

Given a string, reorder its characters so that they appear in order of decreasing frequency. The frequency of a character is the number of times it shows up in the string.

Return any string that is a valid rearrangement. Characters that share the same frequency may appear in any relative order, but every occurrence of a given character must stay grouped together.

Example 1

Input: s = "tree"

Output: "eert"

'e' appears twice while 'r' and 't' appear once each, so 'e' comes first; "eetr" would also be accepted.

Example 2

Input: s = "cccaaa"

Output: "aaaccc"

Both 'a' and 'c' appear three times, so any grouping such as "cccaaa" is valid as long as identical characters are adjacent.

Constraints

1 <= s.length <= 5 * 10^5
s consists of uppercase and lowercase English letters and digits

Count + Bucket Sort by Frequency

Count each character, drop characters into buckets indexed by their count, then rebuild the string from the highest bucket down.

Loading animation…

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

1Count the occurrences of each character with a hash map or a fixed-size array.
2Build buckets indexed by frequency; append each character to bucket[its count].
3Iterate frequencies from the largest down to 1.
4For every character in the current bucket, append that character repeated frequency times to the output.
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)

Time

O(n)

Space

O(n)

n is the length of the string. Bucket sort works because a character's frequency cannot exceed n; a max-heap alternative would cost O(n log m) for m distinct characters.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Regroup The Sticker Sheet is our own problem on the technique behind Sort Characters By Frequency: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free