We need to rearrange the characters in a string so that the most frequent characters come first. Characters with the same frequency can appear in any order relative to each other, but all occurrences of the same character must be grouped together. So "aaabb" is valid for a string where 'a' appears 3 times and 'b' appears 2 times, but "ababa" is not.

A couple of things to notice. First, the problem is case-sensitive: 'A' and 'a' are different characters. Second, digits are also valid characters in the input. Third, when two characters have the same frequency, any ordering between them is acceptable. This flexibility is important because it means we do not need a stable sort or any tiebreaking logic.

The core task boils down to two steps: count how often each character appears, then build a result string by outputting characters from most frequent to least frequent.

Key Constraints:

Intuition

The most straightforward plan: count how many times each character appears, then sort the distinct characters by their frequency in descending order, and finally build the result by repeating each character the appropriate number of times.

Since the alphabet is small (at most 62 distinct characters), sorting is extremely cheap. The expensive part is just the counting and the string building, both of which are O(n). So this approach is already quite efficient despite using a sort.

Algorithm

Example Walkthrough

Code

The sorting approach works well, but we can also use a max-heap to extract characters in frequency order, which is a natural fit for "give me the next most frequent" problems.

Intuition

Instead of sorting all entries at once, we can use a max-heap (priority queue) to always extract the character with the highest frequency. Count the frequencies first, push all character-frequency pairs into a max-heap ordered by frequency, then repeatedly extract the maximum and append that character to the result.

This is a natural fit because the heap gives us the most frequent remaining character in O(log k) time, and we only have at most 62 distinct characters. The approach is also flexible: if the problem changed to "give me only the top 3 most frequent characters," a heap would shine.

Algorithm

Example Walkthrough

Code

Both approaches use comparison-based sorting on the distinct characters. But since every character's frequency is an integer between 1 and n, we can use bucket sort to avoid comparisons entirely and achieve a true O(n) solution.

Intuition

Here is the key insight: the maximum possible frequency of any character is n (the length of the string). So we can create an array of n+1 buckets, where bucket[i] holds all characters that appear exactly i times. After populating the buckets, we just walk from bucket[n] down to bucket[1], appending each character the appropriate number of times. No sorting, no heap, just array indexing.

This is a classic application of bucket sort for problems where the sort key is a bounded integer. Since frequencies range from 1 to n, and we have at most 62 distinct characters spread across these buckets, the entire process is O(n).

Algorithm

Example Walkthrough

Code