重构字符串（767）

767. 重构字符串 - 力扣（LeetCode）

解法：

class Solution {
public:string reorganizeString(string s){string res;//因为1 <= s.length <= 500 ， uint64_t 类型足够uint16_t n = s.size();if (n == 0) {return res;}unordered_map<char, uint16_t> m;for (auto c : s) {m[c] += 1;}vector<pair<char, uint16_t>> v(m.begin(), m.end());//构建最大堆auto compare_f = [](const pair<char, uint16_t> & i1,const pair<char, uint16_t> & i2){return i1.second < i2.second;};//按照key-value ： letter-count，按照count构建最小堆priority_queue<pair<char, uint16_t>, std::vector<pair<char, uint16_t>>, decltype(compare_f)> q (v.begin(), v.end(), compare_f);auto & i = q.top();//如果一个letter，其counter大于一半以上，则肯定无法构建if ((((n & 1) == 1) && (i.second > n/2 + 1)) ||(((n & 1) == 0) && (i.second > n/2))){return  res;}//贪心法，每次从优先队列里面取出count最大的元素while (!q.empty()) {auto  i = move(q.top());q.pop();if (res.size() > 0 && res.back() == i.first) {//如果letter相同，则再取出次多的auto j = move(q.top());q.pop();res += j.first;j.second -= 1;//如果letter count 大于0，则继续插回队列if (j.second > 0) {q.push(j);}}res += i.first;i.second -= 1;//如果letter count 大于0，则继续插回队列if (i.second > 0) {q.push(i);}}return res;}
};

总结：时间复杂度O(N2logN)，空间复杂度O(N)，应用到了最小堆、贪心算法。