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

This post is also available on DEV.