Python 3 Linked list - O(n) time and space - if you want to avoid the O(logN) heap push/pop
Approach\nThis approach is similar to that of a priority queue / heap.\n\nHowever, using a linked list avoid the O(logN) time operations of heappush() and heapp
# Approach\nThis approach is similar to that of a priority queue / heap.\n\nHowever, using a linked list avoid the O(logN) time operations of heappush() and heappop().\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```\n"""\nImplementation of a Node in a linked list.\n"""\nclass Node:\n    def __init__(self, chr, val):\n        self.chr = chr # A letter\n        self.val = val # Store count of a letter \n        self.next = None\n\n"""\nSolution with a linked list\n"""\nclass Solution:\n    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:\n        # Count the letters and store them in an array of 26 \n        counts = [0] * 26\n        for i in s:\n            counts[ord(i)-97] += 1\n\n        # Loop through the counts and construct a linked list that link letters\n        # and their counts in descending order, ignoring letters that have 0 count.\n        # We have as a result:\n        # root = Node(dummy, -1) -> Node(z, 2) -> Node(c, 4) -> Node(a, 1)\n        root = last = Node("dummy", -1)\n        for i in range(len(counts)-1, -1, -1):\n            if counts[i] != 0:\n                last.next = Node(chr(i+97), counts[i])\n                last = last.next\n        root = root.next\n        \n        # We go through the linked list like we do with the priority queue and\n        # add letters into the answer array.\n        k = repeatLimit\n        ans = []\n        # As long as the list is not empty, we keep going.\n        while root: \n            # The current node has count > repeatLimit\n            if root.val > k:\n                # We add the letter into ans (repeatLimit) times and update\n                # the remaining count in the Node.\n                ans.extend([root.chr] * k)\n                root.val -= k\n                \n                # We need to take away one from the next Node (the next largest\n                # letter) and add to the ans as separator.\n                if root.next is None:\n                    # There are no more smaller letters we can use and cannot\n                    # continue adding the letter from the current Node since\n                    # limit is reached.\n                    break\n                else:\n                    # We add the next largest letter from the next Node and\n                    # update remaining count. If remaining count == 0, we remove \n                    # that Node and link Node.next to Node.next.next.\n                    ans.append(root.next.chr)\n                    root.next.val -= 1\n                    if root.next.val == 0:\n                        root.next = root.next.next\n            \n            # The current node has count <= repeatLimit\n            else:\n                # We simply add the letters (count) times into ans and move\n                # on to the next Node. \n                ans.extend([root.chr] * root.val)\n                root = root.next\n\n        return "".join(ans)\n        \n        \n```
['Python3']