Very Concise C++ O(n) Bucket Sort Solution


  • 0
    class Solution {
    public:
        string frequencySort(string s) {
            vector<int> dict(256, 0);
            for (auto ch : s)
                dict[ch]++;
            vector<vector<int>> cache(s.size() + 1);
            for (int i = 0; i < 256; i++) 
                cache[dict[i]].push_back(i);
            string res = "";
            for (int i = cache.size() - 1; i > 0; i--) 
                for (auto ch : cache[i])
                    res += string(i, ch);
            return res;        
        }
    };
    

  • 0
    B

    @zyoppy008 Nice solution! Consider preallocating result. Currently it seems to give MLE however - the problem is that cache size is O(n).


Log in to reply
 

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