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)，應用到了最小堆、貪心算法。