Topics › Strings › Medium String Problems

Sort Characters by Frequency

Easy TUF ID 399 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given a string s, rearrange its characters so that characters with a higher frequency come first, and all copies of the same character are adjacent. For example "tree" has e twice and r, t once each, so "eert" and "eetr" are both valid answers.

The original problem accepts any order among characters that tie on frequency. To make the three implementations below produce identical output and be testable against the same expected strings, we fix the tie-break: among characters with the same count, the one with the smaller character code comes first. So for "tree" the answer is "eert" (r = 114 before t = 116), and for "Aabb" it is "bbAa" because uppercase A (65) sorts before lowercase a (97).

Constraints: 1 ≤ |s| ≤ 5 × 10^5; s consists of uppercase and lowercase English letters and digits, all of which are ASCII.

Example 1

s = "tree"
answer = "eert"        // e×2, then r and t once each

Example 2

s = "cccaaa"
answer = "aaaccc"      // equal counts, so the smaller character a goes first

Example 3

s = "loveleetcode"
answer = "eeeelloocdtv" // e×4; l, o ×2; c, d, t, v ×1

Approach 1: Brute force, count and repeatedly pick the maximum

Intuition. Count how often each character appears. Then build the answer greedily: find the character with the highest remaining count, append that many copies, zero its count, and repeat until nothing is left. Scanning the 128 ASCII slots in increasing order and only replacing the current best on a strictly greater count means that, among tied characters, the smallest code wins, which is exactly our tie-break. This is selection sort applied to the frequency table.

Algorithm.

1. Fill freq[128] from s.
2. Loop: find bestChar with the largest positive freq; if none, stop.
3. Append freq[bestChar] copies of bestChar and set freq[bestChar] = 0.

static String bruteForce(String s) {
    int[] freq = new int[128];
    for (char c : s.toCharArray()) freq[c]++;
    StringBuilder out = new StringBuilder();
    while (true) {
        int bestChar = -1;
        for (int c = 0; c < 128; c++) {
            if (freq[c] > 0 && (bestChar == -1 || freq[c] > freq[bestChar])) bestChar = c;
        }
        if (bestChar == -1) break;                         // nothing left
        for (int k = 0; k < freq[bestChar]; k++) out.append((char) bestChar);
        freq[bestChar] = 0;
    }
    return out.toString();
}

Complexity. Time O(n + k^2) where k ≤ 128 is the alphabet size: counting is O(n), and each of the at most k rounds scans k slots. Space O(1) beyond the output.

Because k is a constant, this is already linear in n. It is called brute force because the selection loop is quadratic in the number of distinct characters and would not scale to a large alphabet.

A small Java detail: freq[c]++ with a char index works because char widens to int automatically, and (char) bestChar narrows the int slot back to a character when appending.

Approach 2: Better, count in a map and sort the distinct characters

Intuition. Collect the distinct characters, sort them with a comparator that puts higher counts first and breaks ties by the character itself, then write each character out count times. The sort replaces the repeated maximum search of Approach 1 and works for any alphabet because the map does not care what the characters are.

Algorithm.

1. Count characters in a HashMap<Character, Integer>.
2. Copy the key set into a list and sort it by (count descending, character ascending).
3. For each character in sorted order, append it count times.

static String better(String s) {
    Map<Character, Integer> freq = new HashMap<>();
    for (char c : s.toCharArray()) freq.merge(c, 1, Integer::sum);
    List<Character> chars = new ArrayList<>(freq.keySet());
    chars.sort((a, b) -> {
        int fa = freq.get(a), fb = freq.get(b);
        if (fa != fb) return Integer.compare(fb, fa);      // higher frequency first
        return Character.compare(a, b);                    // tie: smaller character first
    });
    StringBuilder out = new StringBuilder();
    for (char c : chars) {
        for (int k = 0; k < freq.get(c); k++) out.append(c);
    }
    return out.toString();
}

Complexity. Time O(n + k log k) for counting plus sorting k distinct characters; the expansion is O(n). Space O(k) for the map and the list, plus the output.

Two Java details are worth noticing. The comparator captures freq, which is allowed because the variable is never reassigned (it is effectively final). And Integer.compare(fb, fa), with the arguments swapped, sorts descending without the overflow risk that fb - fa would carry for large values; here the counts are small, but the habit is worth keeping.

Approach 3: Optimal, bucket sort by frequency

Intuition. A frequency is an integer between 1 and n, so instead of sorting the characters by frequency we can place each character directly into the bucket indexed by its count. Bucket f holds the characters that appear exactly f times. Reading the buckets from n down to 1 yields the characters in non-increasing order of frequency, with no comparison sort at all. Within a bucket, characters are inserted in increasing code order because we scan the frequency table from 0 to 127, so the tie-break comes for free.

Algorithm.

1. Fill freq[128] from s.
2. Create n + 1 empty buckets.
3. For each character c with freq[c] > 0, add c to buckets[freq[c]].
4. For f from n down to 1, for each c in buckets[f], append c exactly f times.

static String optimal(String s) {
    int n = s.length();
    int[] freq = new int[128];
    for (char c : s.toCharArray()) freq[c]++;
    List<List<Character>> buckets = new ArrayList<>();      // buckets.get(f) = characters that occur exactly f times
    for (int f = 0; f <= n; f++) buckets.add(new ArrayList<>());
    for (int c = 0; c < 128; c++) {
        if (freq[c] > 0) buckets.get(freq[c]).add((char) c);
    }
    StringBuilder out = new StringBuilder();
    for (int f = n; f >= 1; f--) {
        for (char c : buckets.get(f)) {
            for (int k = 0; k < f; k++) out.append(c);
        }
    }
    return out.toString();
}

Dry run on s = "tree", n = 4:

Complexity. Time O(n + k): counting is O(n), creating and reading the n + 1 buckets is O(n), and the expansion writes exactly n characters. Space O(n + k) for the bucket lists (most of them empty) plus the output.

In practice the bucket version and the sort version are both dominated by the O(n) counting and expansion, since k is tiny. The bucket approach is the one to know because it generalises: it is the standard trick for “sort by frequency” problems, including the top-k frequent elements problem, where it beats a heap.

An alternative optimal variant uses a max-heap (PriorityQueue) keyed by count. It is O(n + k log k) like the sort and is popular because it streams characters out one at a time, which matters in the related problem of reorganising a string so that no two equal characters are adjacent.

Edge cases and pitfalls

• Empty string. The constraints say n ≥ 1, but all three methods return "" gracefully: nothing is counted, no bucket is non-empty, nothing is appended.
• Single character or all characters distinct. "a" returns "a"; "abc" returns "abc" under our tie-break, since all counts are equal and the characters are already in increasing order.
• Case matters. 'A' and 'a' are different characters with separate counts. In "Aabb" the answer is "bbAa": b has count 2, and among the count-1 characters A (65) precedes a (97).
• Digits and other ASCII. They are ordinary characters; "2a2b2" gives "222ab". The freq[128] tables cover all of ASCII; for arbitrary Unicode use the map-based approach or enlarge the tables.
• Tie-breaking. If a judge accepts any order among ties, any of the three methods passes. If you compare approaches against each other in tests, as the Java file does, you need a deterministic rule, otherwise better with an arbitrary tie order could legitimately disagree with optimal.
• Bucket index range. A character can appear at most n times, so n + 1 buckets (indices 0..n) are enough; bucket 0 stays empty. Forgetting the + 1 throws IndexOutOfBoundsException when one character makes up the whole string.
• String building. Append to a StringBuilder; concatenating with += inside the expansion loops would be quadratic.
• Overflow. Counts are at most n ≤ 5 × 10^5, comfortably within int.

Related problems

• Top K Frequent Elements uses the same bucket-by-frequency idea and stops after the first k elements.
• Check if two strings are anagram of each other is the previous problem on the sheet and introduces the frequency array.
• Group Words by Anagrams is another problem where character counts serve as a signature.
• Basic Hashing explains counting with a fixed-size array versus a hash map.