# https://leetcode.com/problems/construct-string-with-repeat-limit

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        cnt = {}
        for ch in s:
            if ch in cnt:
                cnt[ch] += 1
            else:
                cnt[ch] = 1
        result = []
        while len(cnt) > 0:
            key = max(cnt)
            count = cnt[key]
            cnt.pop(key)
            while count > repeatLimit:
                count -= repeatLimit
                for _ in range(repeatLimit):
                    result.append(key)
                if len(cnt) == 0:
                    return ''.join(result)
                sub_key = max(cnt)
                result.append(sub_key)
                cnt[sub_key] -= 1
                if cnt[sub_key] == 0:
                    cnt.pop(sub_key)
            for _ in range(count):
                result.append(key)

        return ''.join(result)