<p>You are given a string <code>s</code> and an integer <code>repeatLimit</code>. Construct a new string <code>repeatLimitedString</code> using the characters of <code>s</code> such that no letter appears <strong>more than</strong> <code>repeatLimit</code> times <strong>in a row</strong>. You do <strong>not</strong> have to use all characters from <code>s</code>.</p>

<p>Return <em>the <strong>lexicographically largest</strong> </em><code>repeatLimitedString</code> <em>possible</em>.</p>

<p>A string <code>a</code> is <strong>lexicographically larger</strong> than a string <code>b</code> if in the first position where <code>a</code> and <code>b</code> differ, string <code>a</code> has a letter that appears later in the alphabet than the corresponding letter in <code>b</code>. If the first <code>min(a.length, b.length)</code> characters do not differ, then the longer string is the lexicographically larger one.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;cczazcc&quot;, repeatLimit = 3
<strong>Output:</strong> &quot;zzcccac&quot;
<strong>Explanation:</strong> We use all of the characters from s to construct the repeatLimitedString &quot;zzcccac&quot;.
The letter &#39;a&#39; appears at most 1 time in a row.
The letter &#39;c&#39; appears at most 3 times in a row.
The letter &#39;z&#39; appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return &quot;zzcccac&quot;.
Note that the string &quot;zzcccca&quot; is lexicographically larger but the letter &#39;c&#39; appears more than 3 times in a row, so it is not a valid repeatLimitedString.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aababab&quot;, repeatLimit = 2
<strong>Output:</strong> &quot;bbabaa&quot;
<strong>Explanation:</strong> We use only some of the characters from s to construct the repeatLimitedString &quot;bbabaa&quot;. 
The letter &#39;a&#39; appears at most 2 times in a row.
The letter &#39;b&#39; appears at most 2 times in a row.
Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString.
The string is the lexicographically largest repeatLimitedString possible so we return &quot;bbabaa&quot;.
Note that the string &quot;bbabaaa&quot; is lexicographically larger but the letter &#39;a&#39; appears more than 2 times in a row, so it is not a valid repeatLimitedString.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= repeatLimit &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        '''
        max heap.
        keep track of the last letter and the number of times repeated
        if it's been repeated three times, find another letter. how?
        keep a hashmap of frequencies.
        push each letter only once into the heap
        when popping off of the heap, see if it's usable.
        if not, pop the next letter off, and push the first letter back in.
        used characters should be subtracted from the hashmap.
        if a char has reached zero, do not put it back into the heap
        '''

        frequencies = defaultdict(int)

        for char in s:
            frequencies[char] += 1
        
        heap = [-ord(char) for char in frequencies.keys()]
        heapq.heapify(heap)

        output = []
        last_char = ""
        count = 0
        while len(s) > 0 and len(heap) > 0:
            largest_char = ""
            heap_top = chr(abs(heapq.heappop(heap)))
            if (last_char == heap_top and count == repeatLimit):
                if len(heap) < 1:
                    break
                largest_char = chr(abs(heapq.heappop(heap)))
                heapq.heappush(heap, -ord(heap_top))
            else:
                largest_char = heap_top
            
            output.append(largest_char)
            if largest_char == last_char:
                count += 1
            else:
                last_char = largest_char
                count = 1

            frequencies[largest_char] -= 1

            if frequencies[largest_char] > 0:
                heapq.heappush(heap, -ord(largest_char))
            
        return "".join(output)
            
571