Construct String With Repeat Limit
Tags: leetcode, dsa, theabbie
Published: 2022-06-13 09:30:38

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

Return _the **lexicographically largest**_ `repeatLimitedString` _possible_.

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

**Example 1:**

**Input:** s = "cczazcc", repeatLimit = 3
**Output:** "zzcccac"
**Explanation:** We use all of the characters from s to construct the repeatLimitedString "zzcccac".
The letter 'a' appears at most 1 time in a row.
The letter 'c' appears at most 3 times in a row.
The letter 'z' 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 "zzcccac".
Note that the string "zzcccca" is lexicographically larger but the letter 'c' appears more than 3 times in a row, so it is not a valid repeatLimitedString.

**Example 2:**

**Input:** s = "aababab", repeatLimit = 2
**Output:** "bbabaa"
**Explanation:** We use only some of the characters from s to construct the repeatLimitedString "bbabaa". 
The letter 'a' appears at most 2 times in a row.
The letter 'b' 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 "bbabaa".
Note that the string "bbabaaa" is lexicographically larger but the letter 'a' appears more than 2 times in a row, so it is not a valid repeatLimitedString.

**Constraints:**

*   `1 <= repeatLimit <= s.length <= 105`
*   `s` consists of lowercase English letters.

**SOLUTION:**

    import heapq
    from collections import Counter
    
    class Solution:
        def lastRepeatLen(self, s, currc, replen):
            n = len(s)
            if n == 0 or currc == s[-1]:
                return replen + 1
            return 1
        
        def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
            ctr = Counter(s)
            op = ""
            replen = 0
            heap = []
            for c in ctr:
                heapq.heappush(heap, (-ord(c), c))
            while len(heap) > 0:
                k, currc = heapq.heappop(heap)
                while len(heap) > 0 and currc not in ctr:
                    k, currc = heapq.heappop(heap)
                if self.lastRepeatLen(op, currc, replen) > repeatLimit:
                    if len(heap) > 0:
                        newk, newc = heapq.heappop(heap)
                        replen = self.lastRepeatLen(op, newc, replen)
                        op += newc
                        ctr[newc] -= 1
                        if ctr[newc] == 0:
                            del ctr[newc]
                        else:
                            heapq.heappush(heap, (newk, newc))
                        heapq.heappush(heap, (k, currc))
                    else:
                        break
                else:
                    replen = self.lastRepeatLen(op, currc, replen)
                    op += currc
                    ctr[currc] -= 1
                    if ctr[currc] == 0:
                        del ctr[currc]
                    else:
                        heapq.heappush(heap, (k, currc))
            return op