Given a non-empty string s and an integer k, rearrange the string such that the same characters are at least distance k from each other.
All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string "".
Example 1:
Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least distance 3 from each other.
Example 2:
Input: s = "aaabc", k = 3
Output: ""
Explanation: It is not possible to rearrange the string.
Example 3:
Input: s = "aaadbbcc", k = 2
Output: "abacabcd"
Explanation: The same letters are at least distance 2 from each other.
// Hash table + greedy + heap
string rearrangeString(string s, int k) { // time: O(nlogn); space: O(n)
if (k == 0) return s;
string res;
int len = (int)s.length();
unordered_map<char, int> m;
priority_queue<pair<int, char> > q;
for (auto& a : s) ++m[a];
for (auto& e : m) q.push({e.second, e.first});
while (!q.empty()) {
vector<pair<int, char>> v;
int cnt = min(k, len);
for (int i = 0; i < cnt; ++i) {
if (q.empty()) return "";
auto t = q.top(); q.pop();
res.push_back(t.second);
if (--t.first > 0) v.push_back(t);
--len;
}
for (auto a : v) q.push(a);
}
return res;
}