[358. Rearrange String k Distance Apart] C++_Priority Queue + Map _ explanation


  • 0

    Similar to the question 621.Task Scheduler
    Solution:

    1. We use map to count the frequencies of each chars in our vector, and use priority queue to sort our pairs according to the chars' frequencies.

    2. For this problem, we use the greedy algorithm. That means when we choose one char, we always try to use the char with the largest frequency among the remaining chars. By this step, we can use the least steps to satisfy the requirements.

    3. While the priority queue is not empty, we choose the top element from the queue, because the distance between two same chars must be k, so we will go to our queue to find out n different chars.

      We have following 2 different case:
      (a) If there is no less than k chars (not the type but the number !) in our queue, if we can find k different types of chars from them, we can deduce 1 from their frequency and then push it into our cache vector if its frequency is not 0.
      /(The cache vector will store the pairs from the queue, and then after one round search, we will push the elements in this vector to our priority queue.)/

      However, if there is less than n types of chars, the problem can be viewed as a pigeon theory problem, like, if we have x items and k containers, and x > k > 0, then at least one container will contain at least 2 or more items. It means that the distance between two same chars will be less than k, this will happen when the priority is empty, then we need directly return "";

      (b) If there is less k chars (the number, not the type) in the queue. We rearrange these remaining chars with above methods and the requirements.
      For example, now we have elements in our cache vector, but the priority queue is empty, so what does that mean? It means that the distance between elements in the cache vector and the same elements in our result string is less than k definitely. So we need return "";

    Code:

    class Compare{
    public:
    bool operator()(pair<char, int> a, pair<char, int> b){
        return (a.second < b.second) || (a.second == b.second && a.first > b.first);
    }
    };
    class Solution {
    public:
    string rearrangeString(string s, int k) {
        if(k == 0) return s;
        unordered_map<char, int> mp;
        string res = "";
        int lens = s.size();
        for(int i = 0; i < s.size(); ++i){
            mp[s[i]]++;
        }
        priority_queue< pair<char, int> , vector<pair<char, int> >, Compare > pq;
        for(auto m : mp){
            pq.push(m);
        }
        while(!pq.empty()){
            vector<pair<char ,int> > tmp_vec;
            int p = min(lens, k);
     /*
     When the number of remaining chars is no less than k, p = k,
     so we need to find out k different types of chars from the queue, otherwise return "";
    
     When the number of remaining chars is less than k, p = lens, so we will still use above method. 
     We want to know whether we could fill our remaining chars within one line. 
     */
            for(int i = 0; i < p; i++, lens--){
                if(pq.empty()) return "";
                auto m = pq.top();
                pq.pop();
                res += m.first;
                if(m.second > 1){
                    m.second--;
                    tmp_vec.push_back(m);
                }
            }
            for(auto v : tmp_vec){
                pq.push(v);
            }
        }
        return res;
    }
    };

Log in to reply
 

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