# C++ O(n) solution using PriorityQueue and HashMap

• ``````    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;
}
``````

• 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 :)

• No, this line and the while loop are both O(1)

``````for (auto& p : mp) q.push(make_pair(p.second, p.first));
``````

since mp.size() < 128

• This doesn't seem to work for my test case:

Input:
"Mymommaalwayssaid,"Lifewaslikeaboxofchocolates.Youneverknowwhatyou'regonnaget."

Output:
oooooooooaaaaaaaaaeeeeeeewwwwssssnnnnyyytttmmmllliiiuurrkkhhggffcc..xvdbYML
Expected:
"aaaaaaaaaoooooooooeeeeeeennnnsssswwwwlllmmmiiitttyyy..hhffrrkkgguuccMvbL"Y,x'd"

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.