Last Updated: 17 Mar, 2021
Sorting Characters By Frequency
Moderate
Asked in companies
You have been given a string ‘S’.
You must return the string ‘S’ sorted in decreasing order based on the frequency of characters.
If there are multiple answers, return any of them.
Example :
Let 'S'= “abAb”.
Here the characters ‘a’ and ‘A’ have frequency 1 and character ‘b’ has frequency ‘2’.
Therefore the sorted string is “bbAa”.
Input Format :
The first line contains a single integer ‘N’ denoting the length of the string ‘S’.
The next line contains the string ‘S’.
Output Format :
The only line contains "true" if the answer is correct otherwise "false".
Note :
You do not need to print anything. It has already been taken care of. Just implement the function.
Approaches
We will sort string ‘s’ as follows:-
- We will first sort string ‘s’ just by ASCII values.
- We will maintain a set ‘ch’ to store the frequency of character and character. We use a set because characters will be sorted in order of frequency, and if two characters have the same frequency, then the character with a lesser ASCII value occurs first.
- We will iterate string ‘s’ to find the frequency of characters:-
- Declare a variable ‘j’ and initialize it with ‘i’.
- While ‘j’ has not reached the end of the string and ‘j’-th character is the same as the ‘i’-th character, increment ‘j’ by 1.
- The frequency of the ‘i’-th character is ‘j’-‘i’. Insert it in set ch with a negative sign.
- Update ‘i’ to ‘j’ - 1 as we have calculated the frequency of all these characters.
- Declare a string ‘ans’ = “” to store the sorted string.
- Iterate the set in order and add each character to ‘ans’ the number of times it had to occur.
- Return ‘ans’.