Construct String With Repeat Limit

Construct String With Repeat Limit

What is this problem about?

In the Construct String With Repeat Limit interview question, you are given a string and a repeatLimit. You need to use the characters from the string to construct the lexicographically largest possible string such that no character appears more than repeatLimit times in a row. You don't have to use all characters.

Why is this asked in interviews?

Microsoft and Google use the Construct String With Repeat Limit coding problem to test a candidate's greedy intuition. It requires a balance between picking the "best" (largest) character and satisfying a constraint. It also evaluates the ability to "save" characters for later use when a limit is reached.

Algorithmic pattern used

This follows the Hash Table, Heap (Priority Queue), String, Greedy interview pattern.

1. Count the frequency of each character.
2. Put the characters and their counts into a Max-Heap (ordered by character value).
3. Always try to pull the largest character from the heap.
4. Append it to the result up to repeatLimit times.
5. If there are more occurrences left, you must append a single instance of the next-largest character from the heap to "break" the sequence before you can use the largest character again.

Example explanation

String: "cczazcc", repeatLimit = 3

1. Counts: z:1, c:5, a:1. Max-Heap: [z, c, a].
2. Take 'z'. Append: "z". Count z=0.
3. Take 'c'. Append 3 'c's: "zccc". Count c=2.
4. We still have 'c' but reached the limit. Take 'a'. Append one 'a': "zccca". Count a=0.
5. Now we can use 'c' again. Append the remaining 2 'c's: "zcccacc". Result: "zcccacc".

Common mistakes candidates make

• Not being greedy enough: Failing to realize that the "breaker" character should only be used once to minimize its impact on the lexicographical order.
• Heap management: Not putting characters back into the heap correctly when they still have remaining counts.
• Tie-breaking: Incorrectly handling the case where no "breaker" character is available (the construction must stop).

Interview preparation tip

Whenever a problem involves "lexicographically largest" and frequency constraints, a Max-Heap combined with a greedy "breaker" strategy is almost always the answer.