leetcode 1405. Longest Happy String 最长快乐字符串-耗时100

Problem: 1405. Longest Happy String 最长快乐字符串

耗时100%，首先按照greedy的策略，每次最多加两个字符，优先队列拿到数量最多的字符，不停的拼起来，延迟放入pre，先拿到cnt和ch再放入pre

最后考虑到某个字符可能很多很多，所以稀疏化，找到其他连续的两个字符，拆出来一个放到最后，然后再次拼起来

Code

using pr = pair<int, char>; class Solution { public: string longestDiverseString(int a, int b, int c) { priority_queue<pr, vector<pr>, decltype(less<pr>())> pq; if(a > 0) pq.push({a, 'a'}); if(c > 0) pq.push({c, 'c'}); if(b > 0) pq.push({b, 'b'}); string tg; int cnt, mx; char ch, mxch; pr pre = {-1, 0}; while(!pq.empty()) { cnt = pq.top().first; ch = pq.top().second; pq.pop(); if(pre.first > 0) pq.push(pre); if(cnt >= 2) { tg += ch; cnt-=2; if(cnt > 0) pre = {cnt, ch}; else pre = {-1, 0}; } else pre = {-1, 0}; tg += ch; } vector<char> tor = {'a', 'b', 'c'}; cnt = pre.first; ch = pre.second; bool find; while(cnt > 0) { find = false; char hcr; int i; for(i = 0; i < tg.size(); i++) { if(ch != tg[i]) { if(i+1 < tg.size() && tg[i+1]==tg[i]) { hcr = tg[i]; find = true; break; } } } if(!find) return tg; tg.erase(tg.begin() + i); tg += hcr; tg += ch; cnt--; if(cnt > 0) { tg += ch; cnt--; } } return tg; } };