Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

problem links: leetcode, geekforgeeks.

Example 1:

Input: s = "tree" 
Output: "eert"

Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input: s = "cccaaa" 
Output: "aaaccc"

Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers. Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input: s = "Aabb" 
Output: "bbAa"

Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect. Note that 'A' and 'a' are treated as two different characters.

Constraints:

1 <= s.length <= 5 * 10<sup>5</sup>
s consists of uppercase and lowercase English letters and digits.

Intuition

The first thing that comes to mind after reading the problem description is, it will need a hashmap or a vector used as a map to solve the problem.

After seeing that you realize that only hashmap will not be sufficient to solve the problem, you need another data structure to sort the frequencies.

There are two options that you can go with:

Using a vector<pair<char, int>> and making a custom sorting function to sort the character according to their frequency.
The second option is using a priority queue to store the char with their frequencies, So we when pop elements one by one we will have elements with the highest frequency at the top always.

You can go with any of the approaches discussed, for now, we don't have any constraints so I go with the second one.

After you have chosen the approach, you need to build the string with a character with the highest frequency at first and the lowest at last. This could be done very easily.

Approach

Declare a hashmap to map char with frequencies and declare and priority.
Iterate over the string and update the frequency of the characters on occurrence.
Iterate over the map now, and push the character with respective frequency in the queue. It is important you push it in <int, char> format. A priority queue will use the first parameter to sort.
Now get the top element in the priority queue and use its frequency and character, push the character in the ans string until the frequency becomes zero.

Solution

c++

class Solution {
public:
    string frequencySort(string s) {

        // Declaration of map and priority queue
        unordered_map<char, int> map;
        priority_queue<pair<int, char>> pq;

        // Mapping the char with the frequency
        for(auto ch: s) map[ch]++;

        // Pushing the char with frequencies in the priority queue
        for(auto it: map){
            pq.push({it.second, it.first});
        }

        string ans = "";

        // Generating the anser string
        while(!pq.empty()){

            auto [freq, ch] = pq.top();
            pq.pop();

            while(freq--) ans.push_back(ch);
        }

        return ans;

    }
};

Java

class Solution {
    public String frequencySort(String s) {


        Map<Character, Integer> map = new HashMap<>();
        PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());

        // Mapping the char with the frequency
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        // Pushing the char with frequencies in the priority queue
        pq.addAll(map.entrySet());

        StringBuilder ans = new StringBuilder();

        // Generating the anser string
        while (!pq.isEmpty()) {
            Map.Entry<Character, Integer> entry = pq.poll();

            int freq = entry.getValue();
            char ch = entry.getKey();

            while (freq-- > 0) {
                ans.append(ch);
            }
        }

        return ans.toString();

    }
}

Time Complexity

The time complexity of this solution is O(nlogn), where n is the length of the string s. This is because the priority queue requires 0(nlogn) time in its worst-case scenario where it will compare an element with each element.

Space Complexity

The space complexity of this solution is O(n), where n is the length of the string s. This is because the solution uses a hash map map and a priority queue pq to store and sort the frequency of each character, respectively.

Thank you for reading the post, I hope this would have helped you to understand the question better and the solution helped you to get a clear understanding of the approach used.

Feel free to drop any comments, I would have to solve your queries and improve my solution.

Sort Characters By Frequency - Leetcode #451