# 358. Rearrange String k Distance Apart

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.
``````

Credits:
Special thanks to @elmirap for adding this problem and creating all test cases.

``````class Solution {
public:
string rearrangeString(string str, int k) {
if (k == 0) return str;
string res;
int len = (int)str.size();
unordered_map<char, int> m;
priority_queue<pair<int, char>> q;
for (auto a : str) ++m[a];
for (auto it = m.begin(); it != m.end(); ++it) {
q.push({it->second, it->first});
}
while (!q.empty()) {
vector<pair<int, int>> 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;
}
};
``````

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

https://leetcode.com/discuss/108174/c-unordered_map-priority_queue-solution-using-cache

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation