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)