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:
- Its next valid position must be no larger than current position.
- 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 {
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;
}
};
```