Leetcode 358 Solution

This article provides solution to leetcode question 358 (rearrange-string-k-distance-apart)
Categories:
Tags:
Access this page by simply typing in "lcs 358" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/rearrange-string-k-distance-apart

Solution

class Solution {
public:
    string rearrangeString(string s, int k) {
        if (k == 0)
            return s;

        unordered_map<char, int> m;
        for (auto ch : s)
            m[ch]++;

        priority_queue<pair<int, char>> q;
        for (auto pair : m)
            q.push(make_pair(pair.second, pair.first));

        string res;
        while (res.size() < s.size())
        {
            vector<pair<int, char>> v;

            int cnt = min((int)s.size() - (int)res.size(), k);
            for (int i = 0; i < cnt; i++)
            {
                if (q.empty())
                    return "";

                auto pair = q.top();
                q.pop();
                res += pair.second;

                if (--pair.first)
                    v.push_back(pair);
            }

            for (auto pair : v)
                q.push(pair);
        }
        return res;
    }
};