Sorting Characters By Frequency
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

Question

Sorting Characters By Frequency

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

Accepted Answer

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

Space Complexity: O(n)Explanation:

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

As we store characters in a set.

Time Complexity: O(nlogn)Explanation:

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

As we are sorting the string.

Python (3.5)

'''



    Time Complexity: O(n*logn)

    Space Complexity: O(n)

    

    Where n is length of the string

    

'''



def sortByFrequency(n, s):



    # Conert string to list

    s = list(s)



    # sort the list to make charcter together.

    s.sort()



    # ch[i][0] : - store the frequency.

    # ch[i][1] : - store the charcter.

    ch = []



    i = 0

    while(i < n):

        j = i



        while(j < n and s[i] == s[j]):

            j += 1



        # store [frequency, charcter]

        ch.append([j-i, s[i]])

        i = j



    ch.sort()



    # to return the answer string.

    ans = []  

    for i in range(len(ch)):



        # Add character with its frequency.

        ans.append(ch[i][1]*ch[i][0])

    

    # convert list to string

    ans = ''.join(ans)  



    return ans

Java (SE 1.8)

/*

    Time Complexity: O(N*log(N))

    Space Complexity: O(N)



    Where N is length of the string

*/



import java.util.Comparator;

import java.util.Arrays;

import java.util.TreeSet;



class Pair

{

    int first;

    char second;

    Pair(int t , char ch)

    {

        first = t;

        second = ch;

    }

}



class myCompare implements Comparator

{

    public int compare(Pair a , Pair b)

    {   

        if(a.first == b.first)

           return Character.compare(a.second, b.second);

        else

           return a.first - b.first;

    }

}



public class Solution 

{   

    public static String sort(String inputString)

    {

        char tempArray[] = inputString.toCharArray();

        

        Arrays.sort(tempArray);

          

        return new String(tempArray);

    }



    public static String sortByFrequency(int n, String s) 

    {

        String ans = "";

        TreeSet ch = new TreeSet<>(new myCompare());



        // Sort the string to make charcaters together

        String temp = sort(s);

        s = temp;



        for (int i = 0; i < n; i++)

        {

            int j = i;

            while (j < n && s.charAt(i) == s.charAt(j))

            {

                j++;

            }



            // Store frequency and character

            ch.add(new Pair(j-i, s.charAt(i)));

            i = j - 1;

        }



        for (Pair it : ch)

        {

            //Concatenating it->first number of it->second character to string

            for(int i=0 ; i            {

               ans += it.second;

            }

        }



        return ans;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N*log(N))

    Space Complexity: O(N)

    

    Where N is length of the string

*/



string sortByFrequency(int n, string s)

{

    string ans = "";

    set> ch;

    

    // Sort the string to make charcaters together

    sort(s.begin(), s.end());

    

    for (int i = 0; i < n; i++)

    {

        int j = i;

        while (j < n && s[i] == s[j])

        {

            j++;

        }



        // Store frequency and character

        ch.insert({j - i, s[i]});

        i = j - 1;

    }



    for (auto it = ch.begin(); it != ch.end(); it++)

    {   

        //Concatenating it->first number of it->second character to string

        ans += string(it->first, it->second); 

    }



    return ans;

}

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 :

Note :

Input Format :

Output Format :

Note :

Constraints :

Top Info Edge Senior Software Engineer Testing interview questions & answers

Popular interview questions of Senior Software Engineer Testing

Top HR questions asked in Info Edge Senior Software Engineer Testing