C++ Solution using multimap (simulating max-heap) ~100 ms

  • 0

    Similar with the idea in the highest voted post. But I think my solution is more scalable for any characters, because I maintain a max-heap for the character, and its count and next valid position. So, we do not need to iterate over the space of characters.
    Here the idea:

    • Calculate the count of each char
    • Make a max-heap using multimap. Node contains count, char, and next valid position
    • While there are nodes in the heap, get the best node that can be appended to the result buffer. The best node satisfies the following two constraints:
      1. Its next valid position must be no larger than current position.
      2. Among those valid nodes, it must have the biggest count.
    • If no such node exist, return empty
    • else, erase the node and insert a new node with count - 1 and next valid position = node.validPos + k. Note that if the count equals to zero, we cannot insert the new node.
    class Solution {
        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);
                if(cand.count > 0) heap.insert(cand);
            return rt;

Log in to reply

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