假设我们有一个非空字符串s和一个整数k；我们必须重新排列字符串，以使相同字符之间的距离至少为k。给定的字符串以小写字母表示。如果没有办法重新排列字符串，那么我们将得到一个空字符串。
因此，如果输入类似于s =“ aabbcc”，k = 3，则输出将为“ abcabc”，这是因为相同的字母彼此之间的距离至少为3。
为了解决这个问题，我们将遵循以下步骤-
ret：=一个空字符串
定义一张映射
n：= s的大小
对于初始化i：= 0，当i <n时，更新（将i增加1），执行-
（将m [s [i]]增加1）
定义一个优先级队列pq
对于在m中的每个键值对，执行-
temp：=有键和键值的一对
将温度插入pq
（增加1）
定义一个双端队列dq
虽然（不是pq为空），但是-
curr：= dq的第一个元素
从dq中删除前元素
如果curr.second> 0，则-
将curr插入pq
curr：= pq的顶部
从pq中删除元素
ret：= ret + curr.first
（将秒数减少1）
在dq的末尾插入curr
如果dq的大小> = k，则-
虽然（不是dq为空，并且dq的第一个元素等于0），但请执行以下操作-
从dq中删除前元素
返回（如果dq为空，则返回，否则为空字符串）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
struct Comparator {
bool operator()(pair<char, int> a, pair<char, int> b) {
return !(a.second > b.second);
}
};
class Solution {
public:
string rearrangeString(string s, int k) {
string ret = "";
unordered_map<char, int> m;
int n = s.size();
for (int i = 0; i < n; i++) {
m[s[i]]++;
}
unordered_map<char, int>::iterator it = m.begin();
priority_queue<pair<char, int<, vector<pair<char, int>>,
Comparator> pq;
while (it != m.end()) {
pair<char, int> temp = {it->first, it->second};
pq.push(temp);
it++;
}
deque<pair<char, int>> dq;
while (!pq.empty()) {
pair<char, int> curr = pq.top();
pq.pop();
ret += curr.first;
curr.second--;
dq.push_back(curr);
// cout << ret << " " << dq.size() << endl;
if (dq.size() >= k) {
curr = dq.front();
dq.pop_front();
if (curr.second > 0)
pq.push(curr);
}
}
while (!dq.empty() && dq.front().second == 0)
dq.pop_front();
return dq.empty() ? ret : "";
}
};
main() {
Solution ob;
cout << (ob.rearrangeString("aabbcc", 3));
}"aabbcc", 3
输出结果
bacbac