Sort Characters By Frequency

The problem. Given a string s, sort its characters in decreasing order of frequency — the characters that appear most come first, with all copies of a character together. Characters with the same frequency can come in any order. Uppercase and lowercase are different characters.

Example

s = "tree"    ->  "eert"  (or "eetr")
s = "cccaaa"  ->  "aaaccc" (or "cccaaa")
s = "Aabb"    ->  "bbAa"   (or "bbaA")

The idea: count, then order the counts

Count every character with a hash map. Now the question is just about ordering the distinct characters by count — a custom comparator (biggest count first) does it in O(k log k) for k distinct characters. Then write each character out as many times as it appears.

Counts are whole numbers from 1 to n, so a bucket sort can replace the comparison sort: bucket f holds the characters that appear exactly f times, and reading the buckets from n down to 1 gives the right order in O(n).

1. Count, then sort the characters by count

1function frequencySort(s) {2  const count = new Map();3  for (const ch of s) count.set(ch, (count.get(ch) ?? 0) + 1);4  const chars = [...count.keys()].sort((a, b) => count.get(b) - count.get(a));   // most frequent first5  return chars.map((ch) => ch.repeat(count.get(ch))).join("");6}

Time O(n + k log k), space O(n), where k is the number of distinct characters — at most 62 letters and digits, so effectively O(n).

2. Bucket sort by frequency

1function frequencySort(s) {2  const count = new Map();3  for (const ch of s) count.set(ch, (count.get(ch) ?? 0) + 1);4  const buckets = Array.from({ length: s.length + 1 }, () => []);   // buckets[f]: characters seen f times5  for (const [ch, f] of count) buckets[f].push(ch);6  let out = "";7  for (let f = s.length; f > 0; f--) for (const ch of buckets[f]) out += ch.repeat(f);8  return out;9}

Time O(n), space O(n). No comparisons at all — the counts themselves are the positions.

Comparing the approaches

For letters only, k is tiny and both are linear in practice; the bucket version is the one to mention when k could be large.

Edge cases to test

Variations