- 重构字符串
给定一个字符串S,检查是否能重新排布其中的字母,使得两相邻的字符不同。
若可行,输出任意可行的结果。若不可行,返回空字符串。
示例 1:
输入: S = “aab”
输出: “aba”
示例 2:
输入: S = “aaab”
输出: “”
C++ 代码
class Solution {
public:
string reorganizeString(string S) {
map<char, int> maps;
for(auto c : S)
{
maps[c]++;
if (maps[c] > (S.size() + 1) / 2)
return "";
}
priority_queue<pair<int, char>> q;
for(auto m : maps)
{
q.push({m.second, m.first});
}
string res = S;
int i = 0;
while(!q.empty()){
char c = q.top().second; // 先放到偶数位置,再放到奇数位置
int cnt = q.top().first;
q.pop();
while (cnt --){
i = i >= S.size() ? 1 : i;
res[i] = c;
i = i + 2;
}
}
return res;
}
};