leetcode 358

 string rearrangeString(string s, int k)
{
    if (k == 0)
        return s;
    string res = "";
    int size = s.size();
    unordered_map<char, int> mp;
    priority_queue<pair<int, char>> pq;
    for (int i = 0; i < s.size(); i++)
        mp[s[i]]++;
    for (auto tmp : mp) {
        pq.push(make_pair(tmp.second, tmp.first));
    }
    while (!pq.empty()) {
        vector<pair<int, char>> cache;
        /*
        当k >= s.size(), 但s中无重复字符时，也存在满足题意的重排字符串。 如果直接取k：
        eg. s = "abc", k = 10, 此时应输出"abc"，但for循环 (10次) 未结束时pq为空，返回 ""， 错误
        */
        int count = min(size, k);   
        for (int i = 0; i < count; i++) {
            if (pq.empty())
                return "";
            pair<int, char> tmp = pq.top();
            pq.pop();
            res += tmp.second;
            size--;
            tmp.first--;
            if (tmp.first > 0)
                cache.push_back(tmp);
        }
        for (int j = 0; j < cache.size(); j++)
            pq.push(cache[j]);
    }
    return res;
}