DEV Community

Alisa Bajramovic
Alisa Bajramovic

Posted on • Updated on

Sorting Characters in a String By Their Frequency

Today's algorithm is:

given a string, sort it in decreasing order based on the frequency of characters.

For example, if you were given the string "tree", the output could be either "eert" or "eetr". If you were given the string "Aabb", the output would be either "bbAa" or "bbaA" (note that "a" and "A" are treated as two different characters.

My initial feeling when I saw this problem was to use a hash map, storing the characters of the string as the keys, and their frequency as values. Then, to build an array of the keys, sorting them by their frequency. And finally, to build a new string, adding characters to it based on the sorted array.

To start this approach, I'll create a hash map, and then I'll loop through the characters of the string and insert them into the hash. If the character has already been seen in the string, I'll increment its value by 1; otherwise, I'll initialize it to equal 1.

function frequencySort(s) {
  let hash = {};
  for (let char of s) {
    if (hash[char]) {
      hash[char]++;
    } else {
      hash[char] = 1;
    }
  }
  //...
}
Enter fullscreen mode Exit fullscreen mode

If the inputted string was "apple", the hash we would have right now would be {"a": 1, "p": 2, "l": 1, "e": 1}. From that hash, we now want to build an array of all of the different keys in the hash. We can easily do that using Object.keys().

function frequencySort(s) {
  let hash = {};
  for (let char of s) {
    if (hash[char]) {
      hash[char]++;
    } else {
      hash[char] = 1;
    }
  }
  let keys = Object.keys(hash);
  //...
}
Enter fullscreen mode Exit fullscreen mode

Now, with the inputted string "apple", keys would equal ["a", "p", "l", "e"]. In order to sort these keys, we'll have to reference their values in the hash. To sort an array using .sort() in a decreasing order, we'll want to write a compare function where larger numbers go to the front.

function frequencySort(s) {
  let hash = {};
  for (let char of s) {
    if (hash[char]) {
      hash[char]++;
    } else {
      hash[char] = 1;
    }
  }
  let keys = Object.keys(hash);
  keys.sort((a, b) => hash[b] - hash[a]);
  //...
}
Enter fullscreen mode Exit fullscreen mode

Now, continuing with the example of "apple", keys would equal ["p", "a", "l", "e"]. At the end of the problem we'll want to return a string, so we can initiate an empty string, and include a line to return the string at the bottom of the function.

function frequencySort(s) {
  let hash = {};
  for (let char of s) {
    if (hash[char]) {
      hash[char]++;
    } else {
      hash[char] = 1;
    }
  }
  let keys = Object.keys(hash);
  keys.sort((a, b) => hash[b] - hash[a]);
  let str = "";
  //...
  return str;
}
Enter fullscreen mode Exit fullscreen mode

Now, the only remaining thing to do is to go through each element in keys and add it to str. However, we want to add each element the number of times that it's found in the hash. There are a number of ways to do this--one of which is to have a counter and a while loop, which I'll do here. As long as the counter is less than the the value of the key in the hash, the key gets added to the string.

function frequencySort(s) {
  let hash = {};
  for (let char of s) {
    if (hash[char]) {
      hash[char]++;
    } else {
      hash[char] = 1;
    }
  }
  let keys = Object.keys(hash);
  keys.sort((a, b) => hash[b] - hash[a]);
  let str = "";
  keys.forEach((k) => {
    let count = 0;
    while (count < hash[k]) {
      str += k;
      count++;
    }
  });
  return str;
}
Enter fullscreen mode Exit fullscreen mode

So, if the input were "apple", the output of this function would be "ppale". I know there are other ways to approach this problem, so feel free to post your favorite approaches in the comments!

Discussion (1)

Collapse
chety profile image
Chety

Hi Alisa,

Thanks for the series. I also solved it with same approach but used different techniques. I am sharing mine , hope it helps someone else.

var frequencySort = function(s) {
    const charCountHash = Array.from(s).reduce((acc,ch) => {
    acc[ch] = (acc[ch] || 0) + 1;
    return acc;
  }, {});

  return Object.entries(charCountHash).sort((a,b) => b[1] - a[1]).reduce((acc,charHash) => {
        const [ch,count] = charHash;
        return acc += ch.repeat(count);        
   }, ""); 
};
Enter fullscreen mode Exit fullscreen mode