priorityqueue + Longest Happy String
Found it quite close to Longest Happy String: https://leetcode.com/problems/longest-happy-string/\n\nFor solution and explanation for it, please see this (Thank
Found it quite close to `Longest Happy String`: https://leetcode.com/problems/longest-happy-string/\n\nFor solution and explanation for it, please see this (Thanks to @lechen999): https://leetcode.com/problems/longest-happy-string/discuss/564248/Python-HEAP-solution-with-explanation\n\nWe first count each char\'s appearing times\nThen use max heap to implement `Longest Happy String`.\nHowever, please pay attention to "the actual appearing time in stack", which we\'ll also need a map to record. Whenever found the prior char `x` exceeds the `repeatLimit` (I simplified it as `k`), we heappop a less appearing char `y` and append it to stack, and `times[y]` should be 1, and clear the `times[x]` because we have a new "stack top". The same for `x` not appearing exceeds `k`. \n\nHope it helps:\n```\nfrom heapq import heapify, heappush, heappop\nfrom collections import defaultdict\n\nclass Solution:\n    def repeatLimitedString(self, string: str, k: int) -> str:\n        """\n        look close to the problem:\n            it\'s  lexicographically largest \n            not "longest"\n        """\n        appear, times = defaultdict(), defaultdict()\n        pq, stack = [], []\n        for s in string:\n            appear[s] = appear.get(s, 0) + 1\n        \n        for s in appear:\n            pq.append((-ord(s), appear[s]))\n        \n        heapify(pq)\n        appear.clear()\n        \n        while pq:\n            char, num = heappop(pq)\n            s = chr(-char)\n            if s in times and times[s] == k: # if reach the repeatedLimit\n                if not pq:\n                    return \'\'.join(stack)\n                char2, num2 = heappop(pq)\n                token = chr(-char2)\n                stack.append(token)\n                if num2 - 1 > 0:\n                    heappush(pq, (char2, num2 - 1))\n                heappush(pq, (char, num))\n                del times[s]\n                times[token] = 1\n                continue\n            if stack and stack[-1] != s:\n                # reset times\n                del times[stack[-1]]\n            stack.append(s)\n            times[s] = times.get(s, 0) + 1\n            \n            if num - 1 > 0:\n                heappush(pq, (char, num - 1))\n        return \'\'.join(stack) \n```
['Heap (Priority Queue)', 'Python']