Problem statement

Given a string s, sort its characters by decreasing frequency — all copies of a character stay together. If two characters have the same frequency, the alphabetically smaller one comes first.

Return the sorted string.

Example 1

Input: s = "tree"
Output: "eert"
Explanation: 'e' appears twice; 'r' before 't' on the tie.

Example 2

Input: s = "cccaaa"
Output: "aaaccc"
Explanation: Tie on frequency 3 — 'a' first alphabetically.

Constraints

• 1 <= s.length <= 40
• Lowercase English letters.

Hints for Sort Characters By Frequency

1. Hint 1

   Count frequencies, then sort the distinct characters by (-count, char).

2. Hint 2

   Rebuild by repeating each character count times.

How to solve Sort Characters By Frequency

Characters only matter in bulk here — every copy of a letter ends up adjacent — so collapse the string to a frequency table first. The answer is then just the distinct characters written out in the right order, each repeated its count times.

Approach

1. Count how often each character appears.
2. Collect the distinct characters.
3. Sort them by (-frequency, character): most frequent first, alphabetically ascending on a tie.
4. Build the result by repeating each character its frequency times, in that order.

Why it works

Since all copies of a character must be contiguous, the output is completely determined by the order of the distinct characters — the rest is mechanical repetition. The comparator fixes that order uniquely: frequency decides, and the alphabetical tie-break removes the remaining freedom, so there is exactly one valid answer and this produces it.

Complexity

• Time — O(n + d log d)
• Space — O(n)

Pitfalls

• The tie-break is required — without it, "cccaaa" could come out as either "cccaaa" or "aaaccc".
• Frequency sorts descending but the character tie-break sorts ascending; getting one direction wrong passes some tests and fails others.
• Build the output from the counts, not by sorting the original characters with a comparator — that is slower and easier to get wrong.
• In a language where a character is an integer, compare the character codes for the tie-break so the ordering really is alphabetical.

Reference solution

Python

from collections import Counter

def frequencySort(s: str) -> str:
    count = Counter(s)
    ordered = sorted(count.items(), key=lambda e: (-e[1], e[0]))
    return "".join(ch * f for ch, f in ordered)

Java

public static String frequencySort(String s) {
    int[] count = new int[128];
    for (char ch : s.toCharArray()) count[ch]++;
    List<Integer> chars = new ArrayList<>();
    for (int c = 0; c < 128; c++) if (count[c] > 0) chars.add(c);
    Collections.sort(chars, (a, b) -> {
        if (count[a] != count[b]) return count[b] - count[a];
        return a - b;
    });
    StringBuilder out = new StringBuilder();
    for (int c : chars) {
        for (int r = 0; r < count[c]; r++) out.append((char) c);
    }
    return out.toString();
}

C++

string frequencySort(string s) {
    int count[128];
    for (int i = 0; i < 128; i++) count[i] = 0;
    for (char ch : s) count[(int) ch]++;
    vector<int> chars;
    for (int c = 0; c < 128; c++) if (count[c] > 0) chars.push_back(c);
    sort(chars.begin(), chars.end(), [&count](int a, int b) {
        if (count[a] != count[b]) return count[a] > count[b];
        return a < b;
    });
    string out;
    for (int c : chars) {
        for (int r = 0; r < count[c]; r++) out += (char) c;
    }
    return out;
}

JavaScript

var frequencySort = function(s) {
    const count = new Map();
    for (const ch of s) count.set(ch, (count.get(ch) || 0) + 1);
    return Array.from(count.entries())
        .sort(function(a, b) { return (b[1] - a[1]) || (a[0] < b[0] ? -1 : 1); })
        .map(function(e) { return new Array(e[1] + 1).join(e[0]); })
        .join("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium