Sort Characters By Frequency

Problem

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

Example 1:

Input: s = "tree"
Output: "eert"
Explanation: 'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input: s = "cccaaa"
Output: "aaaccc"
Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input: s = "Aabb"
Output: "bbAa"
Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

Constraints:

1 <= s.length <= 5 * 10⁵
s consists of uppercase and lowercase English letters and digits.

Solution

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function(s) {
    // store frequency of each value in nums
    let map = {};
    for (let c of s) {
        if (!(c in map)) {
            map[c] = 0;
        }
        map[c]++;
    }

    // bucket sort by frequency
    const bucket = [];
    for (c in map) {
        const freq = map[c];
        while (bucket.length <= freq) {
            bucket.push([]);
        }
        bucket[freq].push(c);
    }

    // construct string ordered by frequency
    let res = "";
    for (let i = bucket.length - 1; i >= 0; --i) {
        for (c of bucket[i]) {
            res += c.repeat(map[c]);
        }
    }
    return res;
};

Store the frequency of each character of s in map. Next, iterate through map, and push each character into the array bucket with the frequency as the index. Finally, construct the output string using bucket by order of frequency (ie. iterate through bucket starting from the back).

Problem​

Solution​

Problem

Solution