Sorting Characters By Frequency

Posted: 17 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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