Sorting Characters By Frequency
Posted: 17 Mar, 2021
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.
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”.
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.
You do not need to print anything; it has already been taken care of. Just implement the function.
1 <= T <= 10 1 <= N <= 1000 Time Limit: 1sec
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’.
Most Frequent Element
Posted: 25 Feb, 2022
Shortest Common Supersequence
Posted: 4 Mar, 2022
Posted: 13 Apr, 2022
Posted: 14 Apr, 2022
Posted: 15 Apr, 2022