string frequencySort(string s) {
unordered_map<char,int> mp;
for (auto& c : s) mp[c]++;
priority_queue<pair<int, char>> q;
for (auto& p : mp) q.push(make_pair(p.second, p.first));
string res;
while (!q.empty()) {
pair<int, char> p = q.top();
q.pop();
res += string(p.first, p.second);
}
return res;
}
C++ O(n) solution using PriorityQueue and HashMap


Technically this algorithm is O(n logn) rather than O(n), and only string limitations make it O(n). Just a warning for anybody who tries to adopt this algorithm for similar problems :) I.e. in the past I had to deal with a problem where input was a vector of strings and the goal was to print top N most popular strings in the array. Same algorithm applies there as well, but it becomes O(n logn)
The point of interest is this line:
for (auto& p : mp) q.push(make_pair(p.second, p.first));
If your input consists only of unique values, then size of mp is n. Push into priority_queue is O(longn). Since you're calling O(logn) n times, overall complexity is O(n logn).
But with strings it IS pretty fast! Thanks for sharing :)

This doesn't seem to work for my test case:
Input:
"Mymommaalwayssaid,"Lifewaslikeaboxofchocolates.Youneverknowwhatyou'regonnaget."Output:
oooooooooaaaaaaaaaeeeeeeewwwwssssnnnnyyytttmmmllliiiuurrkkhhggffcc..xvdbYML
Expected:
"aaaaaaaaaoooooooooeeeeeeennnnsssswwwwlllmmmiiitttyyy..hhffrrkkgguuccMvbL"Y,x'd"