leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2182.cpp (1909B)

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