<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>

from heapq import *

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:

        letters = 'abcdefghijklmnopqrstuvwxyz'

        def letindex(letter) -> int:
            return ord(letter) - ord('a')

        freq = [0] * 26
        for letter in s:
            freq[letindex(letter)] += 1
        
        p1 = 25
        p2 = 25
        ans = []
        while True:
            while p1 > 0 and freq[p1] == 0:
                p1 -= 1
            p2 = p1 - 1
            while p2 >= 0 and freq[p2] == 0:
                p2 -= 1
            
            if freq[p1] == 0:
                break
            
            l1, c1 = letters[p1], freq[p1]
            remove = min(c1, repeatLimit)
            ans += [l1] * remove
            freq[p1] -= remove

            if c1 > repeatLimit:
                if p2 == -1:
                    break
                ans += [letters[p2]]
                freq[p2] -= 1
            elif p2 == -1:
                break
            else:
                p1 = p2
            
        return ''.join(ans)




'''        class ContraStr(str):
            def __lt__(self, s):
                return self.__gt__(s)

        counts = Counter(s)
        heap = []
        for letter, count in counts.items():
            heappush(heap, (ContraStr(letter), count))
        
        ans = ''
        while heap:
            letter, count = heappop(heap)
            remove = min(repeatLimit, count)
            ans += letter * remove
            count -= remove
            if count == 0:
                continue

            stop = False
            while count > 0 and not stop:
                if not heap:
                    stop = True
                else:
                    templet, tempcount = heappop(heap)
                    ans += templet
                    if tempcount != 1:
                        heappush(heap, (templet, tempcount - 1))
                    remove = min(repeatLimit, count)
                    ans += letter * remove
                    count -= remove
            if stop:
                break
        return ans
'''
335