Sort Characters By Frequency

MediumHash Map · Bucket Sort🧩 Bucket & Counting Sort LeetCode #451 ↗Updated Oct 30, 2026

Problem

Rearrange the characters of string s so that characters appearing more often come first. All copies of the same character must sit next to each other. Characters are case-sensitive ('A' and 'a' differ), and when two characters tie, either order is accepted.

Inputs = "tree"Output"eert" ("eetr" also valid)

Inputs = "cccaaa"Output"cccaaa" ("aaaccc" also valid)

Inputs = "Aabb"Output"bbAa" ("bbaA" also valid)

1 ≤ s.length ≤ 5·10⁵ · s has upper/lowercase English letters and digits

Try it yourself

Java

class Solution {
    public String frequencySort(String s) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A frequency can never exceed n, so instead of sorting by count you can drop each character into bucket[count] and read the buckets from high to low — a counting sort on frequencies.

PatternBucket & Counting Sort

Instinct Keys live in a small, known range (letters, frequencies 1..n, bounded values) - index an array by the key instead of comparing, and get O(n).

Memory hack Don't compare, just file it - every value walks straight to its own pigeonhole, then you read the shelves in order.

Open the Bucket & Counting Sort guide →

Approaches

Brute ForceCount, then Sort Every Character

Time O(n log n)Space O(n)

Count frequencies, box all n characters and sort them with a comparator: higher count first, and for equal counts by the character itself so equal letters end up adjacent. Join the sorted characters.

Java

public String frequencySort(String s) {
    Map<Character, Integer> freq = new HashMap<>();
    for (char c : s.toCharArray()) freq.merge(c, 1, Integer::sum);
    Character[] chars = new Character[s.length()];
    for (int i = 0; i < chars.length; i++) chars[i] = s.charAt(i);
    // more frequent first; tie-break on the char keeps equal letters together
    Arrays.sort(chars, (x, y) -> {
        int fx = freq.get(x), fy = freq.get(y);
        return fx != fy ? fy - fx : x - y;
    });
    StringBuilder sb = new StringBuilder();
    for (char c : chars) sb.append(c);
    return sb.toString();
}

Direct, but sorts n boxed characters when only a few distinct ones exist.

BetterCount + Max-Heap of Distinct Characters

Time O(n + k log k)Space O(n + k)

Only the k distinct characters need ordering. Push each one into a max-heap keyed by its count, then pop them in order and append each character count times.

Java

public String frequencySort(String s) {
    int[] freq = new int[128];
    for (char c : s.toCharArray()) freq[c]++;
    PriorityQueue<Character> heap = new PriorityQueue<>((x, y) -> freq[y] - freq[x]);
    for (char c = 0; c < 128; c++) if (freq[c] > 0) heap.add(c);
    StringBuilder sb = new StringBuilder(s.length());
    while (!heap.isEmpty()) {
        char c = heap.poll();
        for (int i = 0; i < freq[c]; i++) sb.append(c);
    }
    return sb.toString();
}

Sorts just k items (k ≤ 62 here), but still pays the heap's log factor.

OptimalBucket Sort by Frequency

Time O(n)Space O(n)

After counting, put each distinct character into bucket[freq] (frequencies range from 1 to n). Walk the buckets from n down to 1 and write every character in a bucket f times. No comparisons at all.

Java

public String frequencySort(String s) {
    int n = s.length();
    int[] freq = new int[128];
    for (char c : s.toCharArray()) freq[c]++;
    StringBuilder[] bucket = new StringBuilder[n + 1]; // bucket[f] = chars seen f times
    for (char c = 0; c < 128; c++) {
        if (freq[c] == 0) continue;
        if (bucket[freq[c]] == null) bucket[freq[c]] = new StringBuilder();
        bucket[freq[c]].append(c);
    }
    StringBuilder sb = new StringBuilder(n);
    for (int f = n; f >= 1; f--) {
        if (bucket[f] == null) continue;
        for (char c : bucket[f].toString().toCharArray())
            for (int i = 0; i < f; i++) sb.append(c);
    }
    return sb.toString();
}

Dry run"tree": t=1, r=1, e=2

f frequency read changed

buckets
·

rt

e

·

·

index = frequency
f=4,3
·

rt

e

·

·
f
empty → skip
f=2
·

rt

e
f
·

·

out = "ee"
f=1
·

rt
f
e

·

·

out = "eert" ✔

Linear time regardless of alphabet size — the textbook answer.

Pro tip

Pre-size the StringBuilder to n; for 5·10⁵ characters, string concatenation in a loop would be quadratic.

At a glance

Level	Approach	Time	Space
Brute Force	Count, then Sort Every Character	`O(n log n)`	`O(n)`
Better	Count + Max-Heap of Distinct Characters	`O(n + k log k)`	`O(n + k)`
Optimal	Bucket Sort by Frequency	`O(n)`	`O(n)`

Common pitfalls

Treating 'A' and 'a' as the same character.
Sorting only by count without a tie-break — equal-count letters can interleave ("abab").
Building the result with += on a String — O(n²) copying.

Interview tips

Ask about the character set: a fixed 128-slot array beats a hash map.
Note that only k distinct chars need ordering, which motivates the heap.
Point out frequencies are bounded by n — that bound is what enables bucket sort.

Pattern

Count + bucket by frequency → order items by how often they occur in O(n).

My notes saved in this browser