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


  • 0
    P
        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;
        }
    

  • 0
    X

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


  • 0
    F

    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


  • 0
    R

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

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

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


Log in to reply
 

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