Re: [閒聊] 每日leetcode

[dont (dont)]

2182. Construct String With Repeat Limit

## 思路

先計算字元出現次數

用max_heap 存 (-ord(ch), freq)

每次pop找下一個要印出的字元, 最多印出repeatLimit 剩下的再塞回heap

如果pop的字元跟前面的相同就先印出另1個字元

e.g {'z': 4, 'x' 3}  repeatLimit=3

zzz x z xx

## Code

```python
class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        counter = Counter(s)
        max_heap = [(-ord(ch), freq) for ch, freq in counter.items()]
        heapq.heapify(max_heap)

        ans = []
        prev = None
        while max_heap:
            ch_ansi, freq = heapq.heappop(max_heap)
            if prev == ch_ansi:
                if not max_heap:
                    break
                next_ch_ansi, next_freq = heapq.heappop(max_heap)
                heapq.heappush(max_heap, (ch_ansi, freq))

                ans.append(chr(-next_ch_ansi))
                if next_freq > 1:
                    heapq.heappush(max_heap, (next_ch_ansi, next_freq-1))
                prev = next_ch_ansi
            else:
                ans.append(chr(-ch_ansi) * min(freq, repeatLimit))
                if freq > repeatLimit:
                    heapq.heappush(max_heap, (ch_ansi, freq-repeatLimit))
                prev = ch_ansi

        return ''.join(ans)
```

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 94.156.205.176 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1734441677.A.505.html
推 oin1104: 大師