Sorting Characters By Frequency

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’.

Try Problem