Sort string based frequency of characters.

Given a string, sort it in descending or ascending order based on the frequency of characters in the string.

Example

Input:
"tree"
"cccaaa"

Output"
"eert" or "eetr"
"aaaccc" or "cccaaa"

In the first example, e appears twice and t and r so the string is sorted as eert or eetr.

In the second example, both the a and c have 3 counts, so aaaccc and cccaaa both are valid output.

In these examples string is sorted in descending order based on the frequency of characters.

Sorting the string based on the frequency of characters.

Implementation

• We will first count the frequency of each characters of the string using an object.
• Then sort these characters in the required order that is ascending or descending based on the frequency count.
• In the end create the new string with these characters which are sorted and return it.

Count the frequency of characters.

Using Array.reduce() we can easily count the frequency of each characters in the string.

We split the string in array of characters and then iterate over each characters in the array and keep checking if it is already present in the object which we are using to count the frequency.

If it is present then increment the count else add it as 1.

const frequency = s.split('').reduce((a, b) => {
   a[b] ? a[b]++ : a[b]=1;
   return a;
 }, {});

Create an array of characters sorted by their frequency count.

We get all the keys of the object in an array which are basically the characters of the string and then sort them based on their frequency.

const sortedCharactersArr = Object.keys(frequency).sort((a, b) => {
 if(frequency[a] > frequency[b]){
    return - 1;
 }
        
 if(frequency[a] < frequency[b]){
    return 1;
 }
        
  return 0;
});

Create a new string with frequency of characters in descending order.

We will iterate over all the character which are stored in the array in sorted order based on their frequency and create a new string from it.

We will be again using the Array.reduce() method to create the sorted string.

const str = sortedCharactersArr.reduce((a, b) => {
   a += b.repeat(frequency[b]);
   return a;
}, "");

Complete Code of sorting a string based on frequency of characters

const frequencySort = function(s) {
    const frequency = s.split('').reduce((a, b) => {
        a[b] ? a[b]++ : a[b]=1;
        return a;
    }, {});
        
    const sortedCharactersArr = Object.keys(frequency).sort((a, b) => {
        if(frequency[a] > frequency[b]){
            return - 1;
        }
        
        if(frequency[a] < frequency[b]){
            return 1;
        }
        
        return 0;
    });
    
    
    const str = sortedCharactersArr.reduce((a, b) => {
        a += b.repeat(frequency[b]);
        return a;
    }, "");
    
    return str;
};

Input:
console.log(frequencySort('tree'));
console.log(frequencySort('cccaaa'));

Output:
'eetr'
'aaaccc'

Time complexity: O(N) + O(NlogN) + O(N) = O(NlogN).
Space complexity: O(N).