Construct String With Repeat Limit — LeetCode 2182 Python Solution

The problem

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.

Example

Input

s = "cczazcc", repeatLimit = 3

Output

"zzcccac"

Explanation

We use all of the characters from s to construct the repeatLimitedString "zzcccac".

Python solution

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        cnt = [0] * 26
        for c in s:
            cnt[ord(c) - ord("a")] += 1
        ans = []
        j = 24
        for i in range(25, -1, -1):
            j = min(i - 1, j)
            while 1:
                x = min(repeatLimit, cnt[i])
                cnt[i] -= x
                ans.append(ascii_lowercase[i] * x)
                if cnt[i] == 0:
                    break
                while j >= 0 and cnt[j] == 0:
                    j -= 1
                if j < 0:
                    break
                cnt[j] -= 1
                ans.append(ascii_lowercase[j])
        return "".join(ans)

Complexity

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2182. Construct String With Repeat Limit is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems