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

"""
Implementation of a Node in a linked list.
"""
class Node:
    def __init__(self, chr, val):
        self.chr = chr # A letter
        self.val = val # Store count of a letter 
        self.next = None

"""
Solution with a linked list
"""
class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        # Count the letters and store them in an array of 26 
        counts = [0] * 26
        for i in s:
            counts[ord(i)-97] += 1

        # Loop through the counts and construct a linked list that link letters
        # and their counts in descending order, ignoring letters that have 0 count.
        # We have as a result:
        # root = Node(dummy, -1) -> Node(z, 2) -> Node(c, 4) -> Node(a, 1)
        root = last = Node("dummy", -1)
        for i in range(len(counts)-1, -1, -1):
            if counts[i] != 0:
                last.next = Node(chr(i+97), counts[i])
                last = last.next
        root = root.next
        
        # We go through the linked list like we do with the priority queue and
        # add letters into the answer array.
        k = repeatLimit
        ans = []
        # As long as the list is not empty, we keep going.
        while root: 
            # The current node has count > repeatLimit
            if root.val > k:
                # We add the letter into ans (repeatLimit) times and update
                # the remaining count in the Node.
                ans.extend([root.chr] * k)
                root.val -= k
                
                # We need to take away one from the next Node (the next largest
                # letter) and add to the ans as separator.
                if root.next is None:
                    # There are no more smaller letters we can use and cannot
                    # continue adding the letter from the current Node since
                    # limit is reached.
                    break
                else:
                    # We add the next largest letter from the next Node and
                    # update remaining count. If remaining count == 0, we remove 
                    # that Node and link Node.next to Node.next.next.
                    ans.append(root.next.chr)
                    root.next.val -= 1
                    if root.next.val == 0:
                        root.next = root.next.next
            
            # The current node has count <= repeatLimit
            else:
                # We simply add the letters (count) times into ans and move
                # on to the next Node. 
                ans.extend([root.chr] * root.val)
                root = root.next

        return "".join(ans)
203