DEV Community

Abubakar Sadiq Ismail
Abubakar Sadiq Ismail

Posted on

Day 5 I4G 10 Days Code Challenge

We are half way Day 5;
Problem: The problem is given a string you should sort it base on the character that has the highest frequency;
E.g given 'aabbbcdee'
'bbb' has highest frequency ,followed by 'aa' and 'ee' (has same frequency), then 'c' and 'd' (has same frequency).
hence the output should be 'bbbaaeecd'
Note for characters that have same frequency they can be in any order; that is the output can as well be 'bbbeeaadc';
Category: Medium we are getting their right!!!

Solution that came to my mind is to use hash map.

Step One
The Map keys are characters and the values are the characters frequency;
E.g of the map for the above Testcase will be;
{'b':3,'a':2,'e':2,'c':1,'d':1}

You can Get this by iterating through the string and creating the property or if it exist incrementing its value.

Step Two
Then create an array of arrays with two values character and the number of time it occurs;
e.g [['b',3],['a',2],['e',2],['c',1],['d',1]]
using Javascript in-built Object.entries(Object) method

Iterate through the array the create another Hash map with the keys as number of time character occurs and the value as array of the characters.
E.g
{'1':['c','d'],'2':['e','a'],3:['b']}

Get all the keys of the map using Object.keys(Object) method;
E.g ['1','2','3'];
Create the returned string
iterate through the keys starting from the highest, get all the characters and multiply it by the time it occur, increment it into the string.
Until the last key.
Return the string

Pretty Long right.

Time Complexity: O(n)
Space Complexity: O(n)
Sort Characters by frequency

Solution Implementation

Top comments (0)