Sort Characters by Frequency

Given a string, sort its characters by how often they occur, most frequent first. Characters with the same frequency keep the order in which they first appear in the string. Uppercase and lowercase letters are different characters.

LeetCode: 451. Sort Characters By Frequency (which allows any order for ties)

Example

Text

Input:  "halalelluejah"    Output: "llllaaahheeuj"
Input:  "aaaabeebccccc"    Output: "cccccaaaabbee"

In the first example, h and e both appear twice; h appears first in the input, so it comes first.

Brute force: count, then sort the distinct characters

Record each character's count and the position where it first appears. Sort the distinct characters by count (descending), then by first position. A LinkedHashMap keeps keys in insertion order, so its keys are already in first-appearance order. List.sort is stable, so sorting by count alone keeps that order for ties.

This lesson treats each Java char (a 16-bit code unit) as one character, which is correct for text without emoji or other characters outside the Basic Multilingual Plane.

Java

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class Main {
    static String frequencySort(String s) {
        Map<Character, Integer> counts = new LinkedHashMap<>(); // char -> count, in first-appearance order
        for (char c : s.toCharArray()) {
            counts.merge(c, 1, Integer::sum);
        }
        List<Map.Entry<Character, Integer>> entries = new ArrayList<>(counts.entrySet());
        entries.sort((a, b) -> Integer.compare(b.getValue(), a.getValue())); // stable: ties keep first-appearance order
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Character, Integer> e : entries) {
            sb.append(String.valueOf(e.getKey()).repeat(e.getValue()));
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(frequencySort("halalelluejah") + " " + frequencySort("aaaabeebccccc"));
    }
}

Output

llllaaahheeuj cccccaaaabbee

Time: O(n + k log k) for k distinct characters. Space: O(n) for the output, O(k) besides it.

Optimal: bucket sort by count

A count is between 1 and n, so the characters can be placed into n + 1 buckets indexed by count, with no comparison sort. Visiting the distinct characters in order of first appearance fills each bucket in the tie order the problem asks for. Then read the buckets from the highest count down.

Java

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class Main {
    static String frequencySort(String s) {
        Map<Character, Integer> counts = new LinkedHashMap<>(); // keys in first-appearance order
        for (char c : s.toCharArray()) {
            counts.merge(c, 1, Integer::sum);
        }
        List<List<Character>> buckets = new ArrayList<>();
        for (int i = 0; i <= s.length(); i++) {
            buckets.add(new ArrayList<>());
        }
        for (Map.Entry<Character, Integer> e : counts.entrySet()) {
            buckets.get(e.getValue()).add(e.getKey());
        }
        StringBuilder result = new StringBuilder(s.length());
        for (int n = buckets.size() - 1; n >= 1; n--) {
            for (char c : buckets.get(n)) {
                result.append(String.valueOf(c).repeat(n));
            }
        }
        return result.toString();
    }

    public static void main(String[] args) {
        System.out.println(frequencySort("halalelluejah") + " " + frequencySort("aaaabeebccccc"));
        System.out.println("\"" + frequencySort("") + "\" " + frequencySort("Aabb"));
    }
}

Output

llllaaahheeuj cccccaaaabbee
"" bbAa

Time: O(n). Space: O(n).

Edge cases

Empty string: an empty result.
All characters distinct: one bucket, and the output is the input.
Uppercase and lowercase: 'A' and 'a' are counted separately.