Sorting Characters By Frequency

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
53 upvotes
Asked in companies
Info Edge India (Naukri.com)AdobeUber

Problem statement

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”.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
6
abcAbc
Sample Output 1 :
true

Explanation Of Sample Output 1 :

The frequency of characters ‘a’ and ‘A’ are 1. The frequency of characters ‘b’ and ‘c’ are 2. 

Therefore the sorted string is “bbccAa”.
Sample Input 2 :
7
gggjhhh
Sample Output 2 :
true
Constraints :
1 <= 'N' <= 10^5

String 'S' consists of both lowercase and uppercase alphabet characters.

Time Limit: 1sec
Follow Up:
Can you solve this in O(N*Log(N)) time?
Hint

Will finding the frequency of each character helps here ?

Approaches (1)
Frequency Of Each Chracter

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

O(N*Log(N)), where ‘N’ denotes the length of the string.

 

As we are sorting the string which takes O(N * Log(N)). Hence, the total time Complexity is O(N * Log(N)).

Space Complexity

O(N), where ‘N’ denotes the length of the string.

 

As we are storing characters in a set, which takes O(N) space.Hence, the total Space Complexity is O(N).

Code Solution
(100% EXP penalty)
Sorting Characters By Frequency
Full screen
Console