# Sorting Characters By Frequency

Posted: 17 Mar, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### You have been given a string ‘S’. You need to sort ‘S’ in increasing order based on the frequency of characters. If two characters have the same frequency then the character with a lesser ASCII value must occur first. Return the sorted string as mentioned above.

##### Example :
``````Let S= “abAb”. Here the character ‘a’ and ‘A’ with frequency 1 and character ‘b’ with frequency ‘2’. Since ‘a’ and ‘A’ have the same frequency the one with a lower ASCII value will occur first. ‘A’ has a lower ASCII value. After ‘A’, ‘a’ will come and finally ‘b’ as it has the highest frequency. Therefore the sorted string is “Aabb”.
``````
##### Note :
``````1. Strings consist of both lowercase and uppercase alphabet characters.
``````
##### Input Format :
``````The first line contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the length of the string ‘S’.

The next line of the test case contains the string ‘S’.
``````
##### Output Format :
``````For each test case print the sorted string.
``````

#### Note :

``````You do not need to print anything; it has already been taken care of. Just implement the function.
``````
##### Constraints :
``````1 <= T <= 10
1 <= N <= 1000

Time Limit: 1sec
``````
Approach 1

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 ‘i’-th character increment ‘j’ by 1.
• The frequency of ‘i’-th character is ‘j’-‘i’. Insert it in set ch.
• 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’.