반복 제한이 있는 구성 문자열

문자열s과 정수repeatLimit가 주어집니다. repeatLimitedString의 문자를 사용하여 문자가 s번 이상 연속으로 나타나지 않도록 새 문자열repeatLimit을 생성합니다. s 의 모든 문자를 사용할 필요는 없습니다.

가능한 한 사전식으로 가장 큰 값repeatLimitedString을 반환합니다.
a와 b가 다른 첫 번째 위치에 문자열a에 해당 문자b의 해당 문자보다 알파벳에서 나중에 나타나는 문자가 있는 경우 문자열a은 문자열b보다 사전식으로 더 큽니다. . 첫 번째min(a.length, b.length) 문자가 다르지 않으면 더 긴 문자열이 사전식으로 더 큰 문자열입니다.

예 1:

입력: s = "cczazcc", repeatLimit = 3
출력: "zzcccac"
설명: s의 모든 문자를 사용하여 repeatLimitedString "zzcccac"을 구성합니다.
문자 'a'는 연속으로 최대 1번 나타납니다.
문자 'c'는 연속으로 최대 3번 나타납니다.
문자 'z'는 연속으로 최대 2번 나타납니다.
따라서 어떤 문자도 한 행에서 repeatLimit 횟수 이상 나타나지 않으며 문자열은 유효한 repeatLimitedString입니다.
문자열은 사전적으로 가장 큰 repeatLimitedString이므로 "zzcccac"을 반환합니다.
문자열 "zzcccca"는 사전식으로 더 크지만 문자 'c'가 연속으로 3번 이상 나타나므로 유효한 repeatLimitedString이 아닙니다.

예 2:

입력: s = "aababab", repeatLimit = 2
출력: "bbabaa"
설명: s의 일부 문자만 사용하여 repeatLimitedString "bbabaa"를 구성합니다.
문자 'a'는 연속으로 최대 2번 나타납니다.
문자 'b'는 연속으로 최대 2번 나타납니다.
따라서 어떤 문자도 한 행에서 repeatLimit 횟수 이상 나타나지 않으며 문자열은 유효한 repeatLimitedString입니다.
문자열은 사전적으로 가장 큰 repeatLimitedString이므로 "bbabaa"를 반환합니다.
문자열 "bbabaaa"는 사전식으로 더 크지만 문자 'a'가 연속으로 2번 이상 나타나므로 유효한 repeatLimitedString이 아닙니다.

제약:

1 <= repeatLimit <= s.length <= 105

s 영문 소문자로 구성되어 있습니다.

해결책:

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