MediumNo. 2182

Construct String With Repeat Limit — LeetCode 2182 Python Solution

Topics
Greedy, Hash Table, String, Counting, Heap (Priority Queue)
Reading time
4 min

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

PythonSolution
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

Time
O(n + |Σ|)
Space · auxiliary
O(|Σ|)

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

Related problems
No.ProblemDifficulty
0767Reorganize StringMedium
0451Sort Characters By FrequencyMedium
0621Task SchedulerMedium
0692Top K Frequent WordsMedium
1054Distant BarcodesMedium
1400Construct K Palindrome StringsMedium

Frequently asked questions

How hard is LeetCode 2182. Construct String With Repeat Limit?

LeetCode 2182. Construct String With Repeat Limit is rated Medium on LeetCode.

What is the time complexity of LeetCode 2182. Construct String With Repeat Limit?

The Python solution on this page runs in O(n + |Σ|).

What is the space complexity of LeetCode 2182. Construct String With Repeat Limit?

The Python solution on this page uses O(|Σ|) auxiliary space.

What topics does LeetCode 2182. Construct String With Repeat Limit cover?

LeetCode 2182. Construct String With Repeat Limit is tagged Greedy, Hash Table, String, Counting and Heap (Priority Queue) on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.