1
class Solution {
2
 public:
3
  string frequencySort(string s) {
4
    unordered_map<char, int> mp;
5
    for (int i = 0; i < s.length(); i++) // get the frequency of every char of the string
6
    {
7
      mp[s[i]]++;
8
    }
9

10
    priority_queue<pair<int, char>> pq; // store the freq and char pair in max heap
11
    for (auto it = mp.begin(); it != mp.end(); it++) {
12
      pq.push({it->second, it->first});
13
    }
14
    string str = "";
15
    int val;
16
    while (!pq.empty()) {
17
      val = pq.top().first; // append the char frequency times
18
      while (val--) {
19
        str.push_back(pq.top().second);
20
      }
21
      pq.pop();
22
    }
23
    return str;
24
  }
25
};