My C++ solution using vector for the heap, and a fixed length separate list to keep out used ones


  • 0
    B

    I use a priority queue to select next char.
    I use a fixed length queue to store latest select characters to prevent from using it again.
    The queue length is k-1
    Whenever I use one element from the priority queue, I will decrease its frequent count by 1, and push to the queue even the count is zero now.
    When I pop the front of the queue, I won't add it to the priority queue if the char frequency is zero.
    I end up spending a lot of time dealing the fixed length queue to deal with corner cases.

    class comp {
    public:
        bool operator()(pair<char,int>& p, pair<char,int>& q) {
            if (p.second != q.second)
                return p.second < q.second;
            return q.first < p.first;
        }
    };
    class Solution {
    public:
        string rearrangeString(string str, int k) {
            map<char, int> m;
            // turn it to dict
            for (auto c:str)
                m[c]++;
            // corner cases
            if (k == 0)
                return str;
            if (!(m.size() >= k || (m.size()==1 && m.begin()->second==1)))
                return "";
            // compose a max-heap
            vector<pair<char,int>> h;
            for (auto pa:m)
                h.push_back(pa);
            make_heap(h.begin(), h.end(), comp());
            // prepare a queue to store thing not appear in next one
            list<pair<char,int>> q;
            string result;
            while (h.size()) {
                pop_heap(h.begin(), h.end(), comp());
                result.append(1, h.back().first);
                h.back().second -= 1;
                q.push_back(h.back());
                h.pop_back();
                if (q.size() > k - 1) {
                    if (q.front().second > 0) {
                        h.push_back(q.front());
                        make_heap(h.begin(), h.end(), comp());
                    }
                    q.pop_front();
                }
            }
            
            if (q.size() > 0) {
                bool allz = true;
                int zcnt = 1;
                for (auto it:q) {
                    if (it.second > 0)
                        allz = false;
                    else
                        zcnt ++;
                }
                if (allz)
                    return result;
                auto iter = q.begin();
                while (iter != q.end()) {
                    if (iter->second > 0) {
                        result.append(1, iter->first);
                        iter->second -= 1;
                    }
    
                    if (iter->second <= 0) {
                        iter = q.erase(iter);
                        continue;
                    }
                    ++iter;
                }
                if (q.size() > 0)           //still remain something
                    return "";
                if (zcnt > 0 && zcnt < k)
                    return "";
            }
            return result;
        }
    };
    

Log in to reply
 

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