2182.cpp (1909B)
1 class Solution { 2 public: 3 string repeatLimitedString(const string &s, int limit) const { 4 int count[27] = {0}; 5 for (const char c : s) 6 count[c & 0x1F]++; 7 8 typedef tuple<char, int> record; 9 priority_queue<record> pq; 10 11 for (int i = 1; i <= 26; i++) { 12 if (!count[i]) continue; 13 pq.emplace('`' + i, count[i]); 14 } 15 16 string res; 17 char last = '~'; 18 while (!empty(pq)) { 19 const auto [c, cnt] = pq.top(); 20 pq.pop(); 21 if (c == last) { 22 if (pq.empty()) break; 23 24 const auto [oc, ocnt] = pq.top(); 25 pq.pop(); 26 pq.emplace(c, cnt); 27 28 res += oc; 29 if (ocnt > 1) pq.emplace(oc, ocnt - 1); 30 31 last = oc; 32 } else { 33 res += string(min(cnt, limit), c); 34 if (cnt > limit) pq.emplace(c, cnt - limit); 35 last = c; 36 } 37 } 38 39 return res; 40 } 41 }; 42 43 // O(1) space, no priority_queue 44 class Solution { 45 public: 46 string repeatLimitedString(const string &s, int limit) const { 47 int count[27] = {0}; 48 for (const char c : s) 49 count[c & 0x1F]++; 50 51 string res; 52 int i; 53 54 for (i = 26; i >= 0; i--) 55 if (count[i]) break; 56 if (count[i] == size(s)) return string(min(limit, count[i]), '`' + i); 57 58 int j = i - 1; 59 while (i > 0) { 60 res += string(min(limit, count[i]), '`' + i); 61 if (limit < count[i]) { 62 while (j >= 0 && !count[j]) 63 j--; 64 if (j < 0) break; 65 66 res += '`' + j; 67 68 count[i] -= limit; 69 count[j]--; 70 } else { 71 i = j; 72 j = i - 1; 73 } 74 } 75 76 return res; 77 } 78 };