文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡書
1. Description
Reorganize String
2. Solution
class Solution {
public:
string reorganizeString(string S) {
int length = S.size();
int maximum = 0;
map<char, int> m;
for(char ch : S) {
m[ch]++;
maximum = max(maximum, m[ch]);
}
if(length - maximum < maximum - 1) {
return "";
}
priority_queue<pair<int, char>> pq;
for(auto item : m) {
pq.push(make_pair(item.second, item.first));
}
string result = "";
while(!pq.empty()) {
pair<int, char> p1 = pq.top();
pq.pop();
result += p1.second;
p1.first--;
if(!pq.empty()) {
pair<int, char> p2 = pq.top();
pq.pop();
result += p2.second;
p2.first--;
if(p2.first) {
pq.push(p2);
}
}
if(p1.first) {
pq.push(p1);
}
}
return result;
}
};
