DSA problem

Sort Characters By Frequency

MediumBucket SortPattern: Bucket Sorttop300AmazonMicrosoftGoogleBloombergApple

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string. Return the sorted string. If two characters have the same frequency, you may return them in any relative order.

The naive approach counts every character with a hash map, converts the entries into a list of (char, count) pairs, sorts that list in descending order by count, and then concatenates each character repeated count times. Sorting costs O(k log k) where k is the number of distinct characters — at most 62 for letters and digits, but the technique generalizes when the alphabet is much larger.

A faster, sorting-free idea uses bucket sort on the frequencies themselves. Observe that no character can appear more than n = len(s) times, so the possible frequencies live in the range [1, n]. Allocate n + 1 buckets where buckets[i] is the list of characters that occur exactly i times.

After populating the buckets in a single pass over the character-count map, walk the buckets from index n down to 1 and, for every character in each non-empty bucket, append it to the result i times. This produces the answer in O(n) total time and O(n) extra space, beating the O(n + k log k) sort-based solution whenever k grows large.

Examples

Example 1

Input: s = "tree"

Output: "eert"

Explanation: The letter 'e' appears twice while 'r' and 't' each appear once. 'eert' or 'eetr' are both valid because the two single-occurrence letters can come in any order.

Example 2

Input: s = "cccaaa"

Output: "aaaccc"

Explanation: Both 'a' and 'c' occur three times. Any ordering that keeps the three a's together and the three c's together is accepted; "aaaccc" and "cccaaa" are both correct.

Example 3

Input: s = "Aabb"

Output: "bbAa"

Explanation: Uppercase and lowercase letters are treated as distinct. 'b' appears twice, while 'A' and 'a' each appear once, so the two b's come first followed by the singletons in any order.

Constraints

1 <= s.length <= 5 * 10^5
s consists of uppercase and lowercase English letters and digits.
The output must be a string with the same characters as the input but reordered by frequency.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

bucket-sorthash-tablestringsortingcounting

Browse all DSA problems