medium

Sort Characters By Frequency

Rearrange a string's characters so the most frequent ones come first.

1. Define the problem

Sort Characters By Frequency

Given a string s, sort it in decreasing order based on the frequency of each character, and return the resulting string. Tally every character into a bucket keyed by how often it occurs, then read the buckets back from the highest count down to the lowest, writing each character out its full count at a time.

Constraints

  • 1 ≤ s.length ≤ 5 × 105
  • s consists of uppercase and lowercase letters and digits

Example

Inputs = "tree"
Output"eetr"

Explanation 'e' appears twice and must come before any single-occurrence character, giving "eetr" (any ordering of the count-1 characters is valid).

2. Know the words first

In plain terms

Frequency
How many times a particular character occurs in the string.
3. Visualize the solution

Count each character, then write out the buckets by count, highest first

Count each character, then write out the buckets by count, highest first
Statusinit

s="tree". Count how often each character appears.

What happens in this step

s = "tree"  (indices 0-3: t, r, e, e)

counts = {}  (empty map, about to tally each character)
Step 1 of 5

Steps to visualize

  1. Count how many times each character occurs in s.
  2. Group characters into buckets keyed by their count.
  3. Walk the buckets from the highest count down to the lowest.
  4. For each bucket, write every character in it out that many times.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Count each character, then write out the buckets by count, highest first
Statusinit

s="tree". Count how often each character appears.

What happens in this step

s = "tree"  (indices 0-3: t, r, e, e)

counts = {}  (empty map, about to tally each character)
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function frequencySort(s) {
  const counts = new Map();

  for (const ch of s) {
    counts.set(ch, (counts.get(ch) || 0) + 1);
  }

  const buckets = new Array(s.length + 1).fill(null).map(() => []);

  for (const [ch, count] of counts) {
    buckets[count].push(ch);
  }

  let result = '';

  for (let count = buckets.length - 1; count >= 1; count--) {
    for (const ch of buckets[count]) {
      result += ch.repeat(count);
    }
  }

  return result;
}
Time
O(n + k)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
s = "tree""eetr"example from the docstring
s = "cccaaa""cccaaa"two characters tied for the highest frequency
s = "Aabb""bbAa"uppercase and lowercase letters treated as distinct characters
s = "a""a"smallest valid input, a single character
s = "abc""abc"every character occurs exactly once
s = "2211""2211"digit characters, already grouped by value
s = "aabbbcccc""ccccbbbaa"three characters with three distinct frequency counts

Keep reading