C++ unordered_map priority_queue solution using cache


  • 31
    S

    key point: using cache during processing heap data.

    new version:

    class Solution {
    public:
        string rearrangeString(string str, int k) {
            if(k == 0) return str;
            int length = (int)str.size(); 
            
            string res;
            unordered_map<char, int> dict;
            priority_queue<pair<int, char>> pq;
            
            for(char ch : str) dict[ch]++;
            for(auto it = dict.begin(); it != dict.end(); it++){
                pq.push(make_pair(it->second, it->first));
            }
            
            while(!pq.empty()){
                vector<pair<int, char>> cache; //store used char during one while loop
                int count = min(k, length); //count: how many steps in a while loop
                for(int i = 0; i < count; i++){
                    if(pq.empty()) return "";
                    auto tmp = pq.top();
                    pq.pop();
                    res.push_back(tmp.second);
                    if(--tmp.first > 0) cache.push_back(tmp);
                    length--;
                }
                for(auto p : cache) pq.push(p);
            }
            return res;
        }
    };
    

    old version:

    class Solution {
        struct mycompare{
            bool operator()(pair<int, char>& p1, pair<int, char>& p2){
                if(p1.first == p2.first) return p1.second > p2.second;
                return p1.first < p2.first;
            }
        };
    public:
        string rearrangeString(string str, int k) {
            if(k == 0) return str;
            unordered_map<char, int> dict;
            for(char ch : str) dict[ch]++;
            int left = (int)str.size();
            priority_queue<pair<int, char>, vector<pair<int, char>>, mycompare > pq;
            for(auto it = dict.begin(); it != dict.end(); it++){
                pq.push(make_pair(it->second, it->first));
            }
            string res;
            
            while(!pq.empty()){
                vector<pair<int, char>> cache;
                int count = min(k, left);
                for(int i = 0; i < count; i++){
                    if(pq.empty()) return "";
                    auto tmp = pq.top();
                    pq.pop();
                    res.push_back(tmp.second);
                    if(--tmp.first > 0) cache.push_back(tmp);
                    left--;
                }
                for(auto p : cache){
                    pq.push(p);
                }
            }
            return res;
        }
    };

  • 0
    A

    Whats the run-time of your algorithm ?
    Each tuple may be inserted multiple times in heap and each insert is log(N)


  • 0
    G

    excellent solution! clean and easy understanding!


  • 9
    T

    I feel that the running time of this algorithm is O(n). The reason is that the only possible characters in the string are lower case letters, which makes the maximum size of the priority queue 26. We are doing one push and pop from the priority queue for each character in the string, which is O(n * (2 * log(26))). This reduces to O(n).

    This is similar to how the other array based solution looks like it would be O(n^2), but it is not because they are doing a linear scan of a constant sized array.


  • -1
    W

    @tjetheron Where the 2 * log(26) comes from? I think it's O(n * log(26)).


  • 1
    S

    This solution is not safe. You can't guarantee that chars in pq will be ordered the same if they have same numbers.


  • 0
    W

    @singku The default comparator compare the count first, and then the char itself. When count is the same, the "bigger" char will have higher priority.


  • 0
    W

    @sxycwzwzq Thanks for sharing. My solution uses multimap to simulate priority queue, and no cache is needed (for pop and push again).

    class Solution {
    public:
        struct Node {
            int count, validPos;
            char ch;
            Node(int count, int validPos, char ch): count(count), validPos(validPos), ch(ch) {}
        };
        
        string rearrangeString(string str, int k) {
            vector<int> mp(26, 0);
            for(char c: str) mp[c-'a']++;
            auto mycomp = [&](const Node& node1, const Node& node2) {return node1.count > node2.count;};
            multiset<Node, decltype(mycomp)> heap(mycomp);
            for(int i = 0; i < 26; i++)
                if(mp[i] != 0) heap.insert(Node(mp[i], 0, i+'a'));
            string rt = "";
            for(int i = 0; i < str.size(); i++) {
                auto iter = heap.begin();
                for(; iter != heap.end() && i < iter->validPos; iter++) {}
                if(iter == heap.end()) return "";
                rt += iter->ch;
                Node cand(iter->count-1, i+k, iter->ch);
                heap.erase(iter);
                if(cand.count > 0) heap.insert(cand);
            }
            return rt;
        }
    };
    

  • 0
    B

    @tjetheron Great Explanation. I figured it out after half an hour.


  • 0
    B
    This post is deleted!

  • 1

    With more comments

    class Solution {
    public:
        using Pair = pair<int, char>;
        string rearrangeString(string s, int K) {
            if (K == 0) return s; // no processing needed
            unordered_map<char, int> m;
            for (char c : s) m[c]++;
            priority_queue<Pair> pq;
            for (auto p : m) pq.emplace(p.second, p.first); // (count, char)
    
            string res;
            while (!pq.empty()) {
                vector<Pair> cache; // store characters we used this round
                // each round, we add K characters to res
                for (int i = 0; i < K; i++) {
                    if (pq.empty()) return ""; // no available characters
                    Pair temp = pq.top(); pq.pop(); // (count, char)
                    res.push_back(temp.second);
                    if (res.size() == s.size()) return res; // done!
                    if (--temp.first > 0) cache.push_back(temp);
                }
                for (Pair& p : cache) pq.push(p);
            }
            return ""; // handle empty string
        }
    };
    

  • 0

    Like your approach using a cache and an inner loop to keep the k-distance.


Log in to reply
 

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