Construct String With Repeat Limit - Leetcode 2182 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
7:01 - Coding Explanation

leetcode 149

#neetcode #leetcode #python

[JamesBond-mqpd]

I am very glad that I was able to solve this problem on my own, even if not perfectly.

my code:

class Solution:
def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
chars = [0] * 26

for c in s:
chars[ord(c) - ord('a')] += 1

heap = []
for i in range(len(chars)):
if chars[i] != 0:
heappush(heap, (- i, chars[i]))

stack = []
while heap:
if stack and stack[-1] == chr(-heap[0][0] + ord('a')):
if len(heap) == 1:
break
f_value, f_count = heappop(heap)
value, count = heappop(heap)
heappush(heap, (f_value, f_count))

c = chr(-value + ord('a'))
stack.append(c)
if count - 1 != 0:
heappush(heap, (value, count - 1))

value, count = heappop(heap)
c = chr(-value + ord('a'))

k = 0

while k < repeatLimit and count != 0:
stack.append(c)
k += 1
count -= 1

if count != 0:
heappush(heap, (value, count))

return "".join(stack)

[AbdoSharafDev]

I believe we can solve it with only a frequency array and a similar while loop with some minor changes and get rid of the Heap because the items are already sorted in the frequency array we just need to loop over them backward.

Btw, happy to see those yellow shirts again.

[soundaryanm]

Ur so consitent, tq for dropping daily question.

[icvetz]

Hey Neetcode, I came up with a very similar solution. I just had a question. What would you do if you needed a max heap and key was an entire string instead of a character? Have you come across any problems where this was necessary? I program primarily in C++, in which you would only need to make the comparator std::greater. But I use Python for interviews, so I am not quite sure... Thanks!

[LasTCursE]

I've solved this without fully understanding it, but after watching this it makes a lot of sense now

[Yahooh]

Would a stack work here as well? With a stack, it'll be more bound to O(n). We can keep the smaller characters at the bottom of stack, then pop off top big characters whenever current character exceeds limit.

[pastori]

wouldn't this be the optimal solution (O(n) space & time)? the editorial doesn't even mention it:
arr = [0] * 26
res = []
for i in range(len(s)):
arr[ord(s[i]) - ord('a')] += 1
i = len(arr) - 1
j = len(arr) - 1
while i >= 0:
if repeatLimit < arr[i]:
n = math.ceil(arr[i] / repeatLimit)
for k in range(n):
while j >= 0 and (arr[j] == 0 or j >= i):
j -= 1

curr_seq_len = min(arr[i], repeatLimit)
arr[i] -= curr_seq_len
for _ in range(curr_seq_len):
res.append(chr(i + ord('a')))
if k == n - 1:
break
if j == -1:
return "".join(res)
res.append(chr(j + ord('a')))
arr[j] -= 1
else:
for _ in range(arr[i]):
res.append(chr(i + ord('a')))
arr[i] = 0
i -= 1
return "".join(res)

[devnull]

Many times I come here just to have the problem read to me :D

[techandmore]

i was very confused because lets consider the case:

caaabaaa, repeat = 3

I don't think your explanation covers that the following would happen:

1. Be greedy (take c): c
2. Be greedy (take b): cb
but now you are left with 6 a's
what to do?

I'll figure out maybe I am stupid

[dazai-gspy]

I could think of the logic and had an intuition to sort or heapify it but couldn't code it > <