Sort Characters By Frequency Solution

Problem

Given a string, rearrange its characters so that the most frequent character appears first. Among characters with equal frequency any ordering is valid, and the same character letter in different cases ('A' vs 'a') counts as two distinct characters.

Input: s = "tree"
Output: "eert"
Explanation: 'e' appears twice and leads the output; 't' and 'r' each appear once and can follow in any order.

A useful counter-example showing case sensitivity: in "Aabb", 'A' and 'a' are separate characters each with frequency 1, while 'b' has frequency 2.

Input: s = "Aabb"
Output: "bbAa"
Explanation: 'b' appears twice; 'A' and 'a' are distinct and each appear once.

Intuition

Once you know each character's frequency, you just need to output characters in descending order of that count. The brute-force way is to sort characters by frequency — simple and correct. A smarter observation: every character frequency must land between 1 and n, so you can skip comparison-based sorting entirely and use bucket sort to group characters by their exact frequency, achieving a true O(n) pass.

Approach 1 — Frequency Map + Sort

Count each character's frequency, then sort the unique characters by frequency descending. Build the result by repeating each character by its count.

Count frequencies with a hash map.
Collect unique characters into a list.
Sort the list by frequency descending.
Concatenate each character repeated by its frequency.

1from collections import Counter
2
3class Solution:
4    def frequencySort(self, s: str) -> str:
5        freq = Counter(s)
6        # sort unique characters by their frequency, highest first
7        sorted_chars = sorted(freq, key=lambda c: -freq[c])
8        return ''.join(c * freq[c] for c in sorted_chars)

Time: O(n log n) — counting is O(n); sorting at most k unique characters is O(k log k), and k ≤ n.
Space: O(n) — the frequency map and result string each hold at most n characters.

Approach 2 — Bucket Sort

Since any character's frequency is between 1 and n, create an array of buckets indexed by frequency. Fill buckets by scanning the frequency map, then read them from highest to lowest to build the result — no comparison-based sort needed.

Count character frequencies.
Create n + 1 buckets; buckets[i] holds every character that appears exactly i times.
Iterate buckets from index n down to 1, appending each character repeated by its bucket index.

1from collections import Counter
2
3class Solution:
4    def frequencySort(self, s: str) -> str:
5        freq = Counter(s)
6
7        # index represents frequency; max possible frequency equals len(s)
8        buckets = [[] for _ in range(len(s) + 1)]
9        for char, count in freq.items():
10            buckets[count].append(char)
11
12        result = []
13        for count in range(len(s), 0, -1):  # high frequency first
14            for char in buckets[count]:
15                result.append(char * count)
16        return ''.join(result)

Time: O(n) — counting is O(n), filling buckets is O(k) ≤ O(n), and reading buckets rebuilds at most n characters total.
Space: O(n) — buckets and result together hold at most n characters.

Complexity Summary

Approach	Time	Space	When to use
Frequency Map + Sort	O(n log n)	O(n)	When simplicity matters; works for any sortable key
Bucket Sort	O(n)	O(n)	When the value range is bounded (character frequencies, small integers)

Common Mistakes

Treating 'A' and 'a' as the same character — the problem is case-sensitive. "Aabb" has frequencies {b:2, A:1, a:1}, not {b:2, a:2}. Normalizing to lowercase before counting produces a wrong answer.
Bucket array sized n instead of n + 1 — if a single character fills the entire string its frequency equals n, requiring index n. An array of size n throws an out-of-bounds error on that case.
String concatenation inside a loop in Java — result += c.repeat(count) inside a loop creates a new String object on each iteration, making the build step O(n²). Always use StringBuilder.append() or collect into a list and join once.
Sorting ascending instead of descending — omitting reverse=True or using the wrong comparator sign puts the rarest characters first, which is the exact opposite of what the problem asks.

Sort Characters By Frequency — Solution