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.

&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 5 * 105
	s consists of uppercase and lowercase English letters and digits.


class Solution:
    def frequencySort(self, s: str) -> str:
        di = Counter(s)
        #it wont strike immediately that this is a heap kind of question.
        heap = []
        heapq.heapify(heap)
        for key,val in di.items():
            heapq.heappush(heap,(-1*val,key))
        # n = len(s)
        res = ""
        # print(heap)
        while(len(heap)):
            val,ch = heapq.heappop(heap)
            res+=(ch*(-1*val))
        return res
class Solution {
    public String frequencySort(String s) {
      HashMap<Character,Integer> hm1=new HashMap<>();
      TreeMap<Integer,ArrayList<Character>> hm2=new TreeMap<>(Collections.reverseOrder());
        for(int i=0;i<s.length();i++)
        {
            char c=s.charAt(i);
            if(hm1.containsKey(c))
            { 
                hm1.put(c,hm1.get(c) + 1);
            }
            else
            {
                hm1.put(c,1);
            }
        }
        for(char c : hm1.keySet())
        {
            if(hm2.containsKey(hm1.get(c)))
            {
                ArrayList<Character> temp=hm2.get(hm1.get(c));
                temp.add(c);
                hm2.put(hm1.get(c),temp);
            }
            else
            {
                ArrayList<Character> temp=new ArrayList<>();
                temp.add(c);
                hm2.put(hm1.get(c),temp);
            }
        }
        StringBuilder sb=new StringBuilder("");
        for(int x :hm2.keySet())
        {
            ArrayList<Character> temp=hm2.get(x);
            for(char c: temp)
            {
                for(int i=0;i<x;i++){
                sb.append(c);
                }
            }
        }
        return sb.toString();
    }
}
class Solution {
public:
    string frequencySort(string s)
    {
        unordered_map<char,int>mp;
        for(int i=0;i<s.length();i++) //get the frequency of every char of the string
        {
            mp[s[i]]++;
        }

        priority_queue<pair<int,char>>pq; //store the freq and char pair in max heap
        for(auto it=mp.begin();it!=mp.end();it++)
        {
            pq.push({it->second,it->first});
        }
        string str="";
        int val;
        while(!pq.empty())
        {
            val=pq.top().first; //append the char frequency times
            while(val--)
            {
                str.push_back(pq.top().second);
            }
            pq.pop();
        }
        return str;

    }
};
var frequencySort = function(s) {
    let obj = {}
    for(const i of s){
        obj[i] = (obj[i] || 0) +1
    }
    let sorted = Object.entries(obj).sort((a,b)=> b[1]-a[1])
    return sorted.map((e)=> e[0].repeat(e[1])).join('')
};
Sort Characters By Frequency