DEV Community

loading...

Sort Characters By Frequency - LeetCode

chakrihacker profile image Subramanya Chakravarthy ・1 min read

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input: "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.

Algorithm

  1. Save the frequencies in a hashtable
  2. Sort the frequencies in decreasing order
  3. rebuild the string based on frequencies

Array Approach:

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function (s) {
  let res = "";
  let map = new Array(128).fill(0);
  for (let i = 0; i < s.length; i++) {
    map[s.charCodeAt(i)]++;
    }
    while(res.length !== s.length) {
        let max = Math.max(...map)
        let idx = map.indexOf(max)
        res = res + String.fromCharCode(idx).repeat(max)
        map[idx] = 0
    }
    return res
};

Optimized Array Approach:

The idea is to store characters based on frequency in array

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function (s) {
  let map = new Array(128).fill(0);
  let max = 0;
  for (let i = 0; i < s.length; i++) {
    map[s.charCodeAt(i)]++;
    max = Math.max(max, map[s.charCodeAt(i)]);
  }
  let hash = new Array(max + 1).fill("");
  for (let i = 0; i < 127; i++) {
    let val = map[i];
    hash[max - val] += String.fromCharCode(i).repeat(val);
  }
  return hash.join("");
};

Using Object:

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function (s) {
    let hashMap = {}
    let res = ""
    for(let i = 0; i < s.length; i++) {
        hashMap[s[i]] = hashMap[s[i]] + 1 || 1
    }
    // sort the characters based on frequency
    let sortedArr = Object.keys(hashMap).sort((a, b) => hashMap[b] - hashMap[a])
    sortedArr.forEach(e => {
        res += e.repeat(hashMap[e])
    })
    return res
};

Discussion

pic
Editor guide