<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:
        # count each number and store in an array of size 26 with 0 being a and 25 being z
        # the idea is that without the constraint of having a repeat limit, we just add as many
        # letters from the largest letter as we can, but since there is a limit, we have to 
        # insert the next biggest letter between sequence of the greatest letters
        # ex: aababab = 4 a and 3 b, limit = 2.  without limit, we will have a string such as bbbaaaa
        # but with the limit we cannot have 3 b in a row, so we insert an a in between to get bbabaaa
        # but since there is a limit of 2 at most, we only get bbabaa
        # go from right of the array, and add to a string, decrementing each number up to the repeat limit
        # and keep doing this while the counts are still greater than 0

        counts = [0] * 26 # a-z
        for ch in s:
            idx = ord(ch) - ord('a')
            counts[idx] += 1
        
        ans = []
        keepChecking = True
        while keepChecking:
            onlyOne = False
            # get largest letter
            idx = 0
            for i in range(25, -2, -1):
                idx = i
                if idx == -1: # went through the entire list and no characters left
                    return "".join(ans)
            
                if counts[i] > 0:
                    # if it was the same as the last character we used, then
                    # it means that we maxed out the limit of the previous character already
                    # so we only want 1 letter of the next largest to break the repeat limit
                    ch = chr(ord('a') + idx)
                    # if ans:
                        # print(ans[-1], ch)
                    if ans and ans[-1] == ch:
                        onlyOne = True
                        continue
                    break
            ch = chr(ord('a') + idx)
            # print(onlyOne, ch)
            addAmount = 1 if onlyOne else min(repeatLimit, counts[idx])
            for _ in range(addAmount):
                ans.append(ch)
                counts[idx] -= 1
            
            # keepChecking = False
            # for i in range(25, -1, -1):
            #     ch = chr(ord('a') + i)
            #     # if last character is the same as this one, then can only add one
            #     onlyOne = False
            #     if ans and ans[-1] == ch:
            #         onlyOne = True
            #     for _ in range(repeatLimit):
            #         if counts[i] > 0:
            #             ch = chr(ord('a') + i)
            #             ans.append(ch)
            #             counts[i] -= 1
            #             keepChecking = True
            #             if onlyOne:
            #                 break
                        
        return "".join(ans)
647