Sort Characters By Frequency

medium string hash map bucket sort

Problem

Given a string s, return the same characters reordered so that the most frequent come first (ties broken arbitrarily).

Inputs = "tree"

Output"eert"

'e' appears 2 times, 't' and 'r' once each.

def frequency_sort(s):
    from collections import Counter
    c = Counter(s)
    buckets = [[] for _ in range(len(s) + 1)]
    for ch, f in c.items(): buckets[f].append(ch)
    out = []
    for f in range(len(buckets) - 1, 0, -1):
        for ch in buckets[f]:
            out.append(ch * f)
    return "".join(out)

function frequencySort(s) {
  const c = new Map();
  for (const ch of s) c.set(ch, (c.get(ch) || 0) + 1);
  const buckets = Array.from({length: s.length + 1}, () => []);
  for (const [ch, f] of c) buckets[f].push(ch);
  let out = "";
  for (let f = buckets.length - 1; f >= 1; f--) {
    for (const ch of buckets[f]) out += ch.repeat(f);
  }
  return out;
}

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> c = new HashMap<>();
        for (char ch : s.toCharArray()) c.merge(ch, 1, Integer::sum);
        List<List<Character>> buckets = new ArrayList<>();
        for (int i = 0; i <= s.length(); i++) buckets.add(new ArrayList<>());
        for (var e : c.entrySet()) buckets.get(e.getValue()).add(e.getKey());
        StringBuilder sb = new StringBuilder();
        for (int f = buckets.size() - 1; f >= 1; f--) {
            for (char ch : buckets.get(f)) {
                for (int k = 0; k < f; k++) sb.append(ch);
            }
        }
        return sb.toString();
    }
}

string frequencySort(string s) {
    unordered_map<char, int> c;
    for (char ch : s) c[ch]++;
    vector<vector<char>> buckets(s.size() + 1);
    for (auto& e : c) buckets[e.second].push_back(e.first);
    string out;
    for (int f = (int)buckets.size() - 1; f >= 1; f--) {
        for (char ch : buckets[f]) out.append(f, ch);
    }
    return out;
}

Explanation

We want the characters reordered so the most frequent appear first. Instead of a comparison sort, this solution uses bucket sort, which groups characters by how often they occur and is very fast.

First we count each character with a Counter. Then we make buckets, a list of lists indexed by frequency: buckets[f] holds every character that appears exactly f times.

To build the answer we walk the buckets from the highest frequency down to 1. For each character in a bucket of frequency f, we append that character repeated f times (ch * f), then join everything into the final string.

Walking high-to-low guarantees frequent characters land at the front. Ties (characters with the same frequency) just come out in bucket order, which the problem allows.

Example: "tree" counts as e:2, t:1, r:1. Bucket 2 holds e, bucket 1 holds t and r. Emitting bucket 2 then bucket 1 gives "ee" + "t" + "r" = "eert".

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