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 a 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.length, b.length)
characters do not differ, then the longer string is the lexicographically larger one.
Example 1:
Input: s = "cczazcc", repeatLimit = 3
Output: "zzcccac"
Explanation: We use all of the characters from s to construct the repeatLimitedString "zzcccac".
The letter 'a' appears at most 1 time in a row.
The letter 'c' appears at most 3 times in a row.
The letter 'z' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "zzcccac".
Note that the string "zzcccca" is lexicographically larger but the letter 'c' appears more than 3 times in a row, so it is not a valid repeatLimitedString.
Example 2:
Input: s = "aababab", repeatLimit = 2
Output: "bbabaa"
Explanation: We use only some of the characters from s to construct the repeatLimitedString "bbabaa".
The letter 'a' appears at most 2 times in a row.
The letter 'b' appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return "bbabaa".
Note that the string "bbabaaa" is lexicographically larger but the letter 'a' appears more than 2 times in a row, so it is not a valid repeatLimitedString.
Constraints:
-
1 <= repeatLimit <= s.length <= 105
-
s
consists of lowercase English letters.
SOLUTION:
import heapq
from collections import Counter
class Solution:
def lastRepeatLen(self, s, currc, replen):
n = len(s)
if n == 0 or currc == s[-1]:
return replen + 1
return 1
def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
ctr = Counter(s)
op = ""
replen = 0
heap = []
for c in ctr:
heapq.heappush(heap, (-ord(c), c))
while len(heap) > 0:
k, currc = heapq.heappop(heap)
while len(heap) > 0 and currc not in ctr:
k, currc = heapq.heappop(heap)
if self.lastRepeatLen(op, currc, replen) > repeatLimit:
if len(heap) > 0:
newk, newc = heapq.heappop(heap)
replen = self.lastRepeatLen(op, newc, replen)
op += newc
ctr[newc] -= 1
if ctr[newc] == 0:
del ctr[newc]
else:
heapq.heappush(heap, (newk, newc))
heapq.heappush(heap, (k, currc))
else:
break
else:
replen = self.lastRepeatLen(op, currc, replen)
op += currc
ctr[currc] -= 1
if ctr[currc] == 0:
del ctr[currc]
else:
heapq.heappush(heap, (k, currc))
return op
Top comments (0)