DEV Community 👩‍💻👨‍💻

Subramanya Chakravarthy
Subramanya Chakravarthy

Posted on

Sort Characters By Frequency - LeetCode

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
};

Top comments (0)

DEV

Thank you.

 
Thanks for visiting DEV, we’ve worked really hard to cultivate this great community and would love to have you join us. If you’d like to create an account, you can sign up here.