Leetcode 358 Solution

This article provides solution to leetcode question 358 (rearrange-string-k-distance-apart)

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; } };