NeetCode #810LC-2182MediumGreedy
← Back to All Problems#810 · #2182 · Construct String With Repeat Limit(构造限制重复的字符串)
📌 Problem Statement & Constraints
Given a string
s and an integer repeatLimit, construct the lexicographically largest string from the characters of s such that no character is repeated more than repeatLimit times consecutively. You do not have to use all characters. Constraints: 1 <= s.length <= 10^5, 1 <= repeatLimit <= s.length, s consists of lowercase English letters.💡 Core Algorithmic Approaches
- Greedily prefer the largest available character, because lexicographic order is decided at the first differing position.
- Count the 26 letters, then repeatedly take up to
repeatLimitcopies of the current largest letter. - If that letter still has leftovers, place one copy of the next smaller available letter as a separator, which resets the run length for the big letter.
- If no smaller letter exists, no legal continuation remains, so stop. This greedy is optimal because every emitted character is the largest that can legally follow.
💻 Benchmark Python3 Implementation
class Solution:
def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
cnt = [0] * 26
for ch in s:
cnt[ord(ch) - ord("a")] += 1
res = []
i = 25 # start from the largest letter
while i >= 0:
if cnt[i] == 0:
i -= 1
continue
take = min(cnt[i], repeatLimit)
res.append(chr(ord("a") + i) * take)
cnt[i] -= take
if cnt[i] > 0:
j = i - 1 # find a smaller separator letter
while j >= 0 and cnt[j] == 0:
j -= 1
if j < 0:
break # nothing left to break the run
res.append(chr(ord("a") + j))
cnt[j] -= 1
else:
i -= 1
return "".join(res)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n + 26 * distinct letters): each character is emitted once and the separator scan is bounded by 26.
💾 Space Complexity
O(1) beyond the output: a 26-element counter.
⚠️ Interview Pitfalls & Follow-ups
- Decrementing
iafter placing a separator: the big letter still has leftovers, so the loop must stay atito emit more of it next round. - Using all
cnt[i]copies at once: exceedingrepeatLimitin a row is illegal, so the take is capped. - Stopping when the separator is exhausted by count 0 but exists later: the scan
jmust skip letters with zero count, not stop at the first zero. - Greedily taking the smallest letter as separator: any smaller letter works, and scanning down from
i-1finds the largest legal separator, preserving lexicographic optimality.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.