aboutsummaryrefslogtreecommitdiff
path: root/construct_string_repeat_lim.py
diff options
context:
space:
mode:
Diffstat (limited to 'construct_string_repeat_lim.py')
-rw-r--r--construct_string_repeat_lim.py49
1 files changed, 49 insertions, 0 deletions
diff --git a/construct_string_repeat_lim.py b/construct_string_repeat_lim.py
new file mode 100644
index 0000000..f9c1cd5
--- /dev/null
+++ b/construct_string_repeat_lim.py
@@ -0,0 +1,49 @@
+# 2182. Construct String With Repeat Limit
+import heapq
+from collections import Counter
+
+"""
+you are given a string 's' and an integer 'repeatLimit'. construct a new
+string 'repeatLimitedString' using the characters of 's' such that no letter
+appears more than 'repeatLimit' times in a row. you do not have to use all
+characters from 's'. return the lexicographically largest
+'repeatLimitedString' possible. a string 'a' is lexicographically larger than
+string 'b' if in the first position where 'a' and 'b' differ, string 'a' has
+a letter that appears later in the alphabet than the corresponding letter in
+'b'. if the first 'min(a.len, b.len)' characters do not differ, then the
+longer string is the lexicographically larger one
+"""
+
+
+class Solution(object):
+ def repeatLimitedString(self, s, repeatLimit):
+ """
+ :type s: str
+ :type repeatLimit: int
+ :rtype: str
+ """
+ pq = [(-ord(k), v) for k, v in Counter(s).items()]
+ heapq.heapify(pq)
+ ans = []
+ while pq:
+ k, v = heapq.heappop(pq)
+ if ans and ans[-1] == k:
+ if not pq:
+ break
+ kk, vv = heapq.heappop(pq)
+ ans.append(kk)
+ if vv - 1:
+ heapq.heappush(pq, (kk, vv - 1))
+ heapq.heappush(pq, (k, v))
+ else:
+ m = min(v, repeatLimit)
+ ans.extend([k] * m)
+ if v - m:
+ heapq.heappush(pq, (k, v - m))
+ return "".join(chr(-x) for x in ans)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.repeatLimitedString(s="cczazcc", repeatLimit=3))
+ print(obj.repeatLimitedString(s="aababab", repeatLimit=2))