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
- Save the frequencies in a hashtable
- Sort the frequencies in decreasing order
- 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)