Sort Characters By Frequency

Problem Statement

Given a string s, return it rearranged so characters are grouped and ordered by decreasing frequency (any order among equal frequencies is accepted).

Example

Input:  s = "tree"
Output: "eert"  (or "eetr")

Approach

Count each character’s frequency with a hash map. Sort the distinct characters by count descending, then build the answer by repeating each character its count number of times. (A bucket-by-frequency variant runs in O(n).)

Complexity

• Time: O(n + k log k), k = distinct characters
• Space: O(n)

Solution Code

Python

from collections import Counter
def frequencySort(s):
    freq = Counter(s)
    return "".join(c * n for c, n in freq.most_common())

Java

String frequencySort(String s) {
    Map<Character, Integer> freq = new HashMap<>();
    for (char c : s.toCharArray()) freq.merge(c, 1, Integer::sum);
    List<Character> keys = new ArrayList<>(freq.keySet());
    keys.sort((a, b) -> freq.get(b) - freq.get(a));
    StringBuilder sb = new StringBuilder();
    for (char c : keys) for (int i = 0; i < freq.get(c); i++) sb.append(c);
    return sb.toString();
}

C++

string frequencySort(string s) {
    unordered_map<char, int> freq;
    for (char c : s) freq[c]++;
    vector<pair<int, char>> items;
    for (auto& kv : freq) items.push_back({kv.second, kv.first});
    sort(items.begin(), items.end(), greater<>());
    string res;
    for (auto& it : items) res += string(it.first, it.second);
    return res;
}

Key Takeaways

• Count first, then sort the distinct keys by frequency — not the whole string.
• Bucket sort by frequency gives an O(n) alternative.
• Reference: LeetCode 451 (Sort Characters By Frequency).