C++ solution - reverse map to track ordered occurance


  • 0
    P

    smap - tracks char to intenger mapping (hash map).
    imap - track integer to char mapping (map)

    class Solution {
    public:
        string frequencySort(string s) {
            unordered_map<char, int> smap;
            map<int, unordered_set<char>, std::greater<int>> imap;
            
            for (int i = 0; i < s.length(); i++) {
                if (!smap.count(s[i])) {
                    smap.insert(make_pair(s[i], 1));
                    if (imap.count(1)) {
                        imap[1].insert(s[i]);
                    } else {
                        unordered_set<char> uset;
                        uset.insert(s[i]);
                        imap.insert(make_pair(1, uset));
                    }
                } else {
                    if (imap.count(smap[s[i]])) {
                        if (imap[smap[s[i]]].count(s[i])) {
                            imap[smap[s[i]]].erase(s[i]);
                            if (!imap[smap[s[i]]].size()) {
                                imap.erase(smap[s[i]]);
                            }
                        }
                    }
                
                    smap[s[i]]++;
                    if (imap.count(smap[s[i]])) {
                        imap[smap[s[i]]].insert(s[i]);
                    } else {
                        unordered_set<char> uset;
                        uset.insert(s[i]);
                        imap.insert(make_pair(smap[s[i]], uset));
                    }
                }
            }
        
            string result;
            for (auto ielem : imap) {
                int count = ielem.first;
                unordered_set<char> uset = ielem.second;
                for (auto cchar : uset) {
                    string str(count, cchar);
                    result += str;
                }
            }
            
            return result;
        }
    };

Log in to reply
 

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