leetcode

commit 401e1ac01777d2cab3303a6e5f6c1bd7ceb065cc
parent 022db97f36ed64d75a85eea481f3fc33beade83e
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 16 Feb 2024 22:08:10 +0000

1 Random Problem

Diffstat:
A
Problems/2182.cpp
 | 
78
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 79 insertions(+), 0 deletions(-)
diff --git a/Problems/2182.cpp b/Problems/2182.cpp
@@ -0,0 +1,78 @@
+class Solution {
+  public:
+    string repeatLimitedString(const string &s, int limit) const {
+        int count[27] = {0};
+        for (const char c : s)
+            count[c & 0x1F]++;
+
+        typedef tuple<char, int> record;
+        priority_queue<record> pq;
+
+        for (int i = 1; i <= 26; i++) {
+            if (!count[i]) continue;
+            pq.emplace('`' + i, count[i]);
+        }
+
+        string res;
+        char last = '~';
+        while (!empty(pq)) {
+            const auto [c, cnt] = pq.top();
+            pq.pop();
+            if (c == last) {
+                if (pq.empty()) break;
+
+                const auto [oc, ocnt] = pq.top();
+                pq.pop();
+                pq.emplace(c, cnt);
+
+                res += oc;
+                if (ocnt > 1) pq.emplace(oc, ocnt - 1);
+
+                last = oc;
+            } else {
+                res += string(min(cnt, limit), c);
+                if (cnt > limit) pq.emplace(c, cnt - limit);
+                last = c;
+            }
+        }
+
+        return res;
+    }
+};
+
+// O(1) space, no priority_queue
+class Solution {
+  public:
+    string repeatLimitedString(const string &s, int limit) const {
+        int count[27] = {0};
+        for (const char c : s)
+            count[c & 0x1F]++;
+
+        string res;
+        int i;
+
+        for (i = 26; i >= 0; i--)
+            if (count[i]) break;
+        if (count[i] == size(s)) return string(min(limit, count[i]), '`' + i);
+
+        int j = i - 1;
+        while (i > 0) {
+            res += string(min(limit, count[i]), '`' + i);
+            if (limit < count[i]) {
+                while (j >= 0 && !count[j])
+                    j--;
+                if (j < 0) break;
+
+                res += '`' + j;
+
+                count[i] -= limit;
+                count[j]--;
+            } else {
+                i = j;
+                j = i - 1;
+            }
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -987,6 +987,7 @@ for solving problems.
 |  2177  |   Medium   | [Find Three Consecutive Integers That Sum to a Given Number](Problems/2177.cpp)                    |
 |  2178  |   Medium   | [Maximum Split of Positive Even Integers](Problems/2178.cpp)                                       |
 |  2181  |   Medium   | [Merge Nodes in Between Zeros](Problems/2181.cpp)                                                  |
+|  2182  |   Medium   | [Construct String With Repeat Limit](Problems/2182.cpp)                                            |
 |  2186  |   Medium   | [Minimum Number of Steps to Make Two Strings Anagram II](Problems/2186.cpp)                        |
 |  2187  |   Medium   | [Minimum Time to Complete Trips](Problems/2187.cpp)                                                |
 |  2192  |   Medium   | [All Ancestors of a Node in a Directed Acyclic Graph](Problems/2192.cpp)                           |