⚡Flashcard Drill➔
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

  1. Greedily prefer the largest available character, because lexicographic order is decided at the first differing position.
  2. Count the 26 letters, then repeatedly take up to repeatLimit copies of the current largest letter.
  3. 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.
  4. 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 i after placing a separator: the big letter still has leftovers, so the loop must stay at i to emit more of it next round.
  • Using all cnt[i] copies at once: exceeding repeatLimit in a row is illegal, so the take is capped.
  • Stopping when the separator is exhausted by count 0 but exists later: the scan j must 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-1 finds 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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems