Construct String With Repeat Limit LeetCode solution in Python

1
from heapq import heapify, heappush, heappop
2
from collections import defaultdict
3

4

5
class Solution:
6
    def repeatLimitedString(self, string: str, k: int) -> str:
7
        """
8
        look close to the problem:
9
            it's  lexicographically largest
10
            not "longest"
11
        """
12
        appear, times = defaultdict(), defaultdict()
13
        pq, stack = [], []
14
        for s in string:
15
            appear[s] = appear.get(s, 0) + 1
16

17
        for s in appear:
18
            pq.append((-ord(s), appear[s]))
19

20
        heapify(pq)
21
        appear.clear()
22

23
        while pq:
24
            char, num = heappop(pq)
25
            s = chr(-char)
26
            if s in times and times[s] == k:  # if reach the repeatedLimit
27
                if not pq:
28
                    return "".join(stack)
29
                char2, num2 = heappop(pq)
30
                token = chr(-char2)
31
                stack.append(token)
32
                if num2 - 1 > 0:
33
                    heappush(pq, (char2, num2 - 1))
34
                heappush(pq, (char, num))
35
                del times[s]
36
                times[token] = 1
37
                continue
38
            if stack and stack[-1] != s:
39
                # reset times
40
                del times[stack[-1]]
41
            stack.append(s)
42
            times[s] = times.get(s, 0) + 1
43

44
            if num - 1 > 0:
45
                heappush(pq, (char, num - 1))
46
        return "".join(stack)