#2182

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Construct String With Repeat Limit

Construct a lexicographically largest string from a given string with no letter appearing more than a repeatLimit times in a row.

hash table string greedy heap priority queue counting

Problem Statement

You are given a string s and an integer repeatLimit. Your task is to construct a new string repeatLimitedString using the characters from s such that no letter appears more than repeatLimit times consecutively. You don't need to use all characters from s.

Return the lexicographically largest valid repeatLimitedString possible, ensuring the repeatLimit constraint is satisfied. A string a is lexicographically larger than string b if at the first differing position, a has a letter that comes later in the alphabet than b.

Examples

Example 1

Input: s = "cczazcc", repeatLimit = 3

Output: "zzcccac"

We use all of the characters from s to construct the repeatLimitedString "zzcccac". The letter 'a' appears at most 1 time in a row. The letter 'c' appears at most 3 times in a row. The letter 'z' appears at most 2 times in a row. Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString. The string is the lexicographically largest repeatLimitedString possible so we return "zzcccac". Note that the string "zzcccca" is lexicographically larger but the letter 'c' appears more than 3 times in a row, so it is not a valid repeatLimitedString.

Example 2

Input: s = "aababab", repeatLimit = 2

Output: "bbabaa"

We use only some of the characters from s to construct the repeatLimitedString "bbabaa". The letter 'a' appears at most 2 times in a row. The letter 'b' appears at most 2 times in a row. Hence, no letter appears more than repeatLimit times in a row and the string is a valid repeatLimitedString. The string is the lexicographically largest repeatLimitedString possible so we return "bbabaa". Note that the string "bbabaaa" is lexicographically larger but the letter 'a' appears more than 2 times in a row, so it is not a valid repeatLimitedString.

Constraints

1 <= repeatLimit <= s.length <= 105
s consists of lowercase English letters.

Solution Approach

Greedy Approach

Start by sorting the characters of the string in descending order. Then, use a greedy approach to construct the result string, ensuring that no character appears more than repeatLimit times in a row.

Heap for Efficient Character Selection

To efficiently manage the selection of characters, use a max heap (priority queue). This allows for quick access to the lexicographically largest character available that hasn't been used more than repeatLimit times consecutively.

Validation of Constraints

As you construct the string, continuously check that the number of consecutive repetitions of any character does not exceed repeatLimit. If it does, adjust the selection accordingly.

Complexity Analysis

Metric	Value
Time	O(N \cdot \log K)
Space	O(K)

The time complexity of the solution is O(N * log K), where N is the length of the string and K is the number of unique characters. The space complexity is O(K), as we use a hash table or heap to store the character frequencies and manage the greedy selection process.

What Interviewers Usually Probe

Can the candidate explain how a greedy approach ensures the largest lexicographical string while respecting the repeatLimit?
Does the candidate recognize the importance of using a max heap for efficient character selection?
Is the candidate able to demonstrate an understanding of the trade-offs between greedy strategies and maintaining constraints?

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle the repeatLimit constraint when appending characters, leading to invalid strings.
Overcomplicating the problem by not using the heap or hash table efficiently for character management.
Misunderstanding the lexicographical order, leading to suboptimal solutions where smaller characters are selected first.

Follow-up variants

What if the repeatLimit was higher than the length of the string? How would the solution change?
How does this solution handle edge cases like an empty string or a string where all characters are the same?
What if the characters in the string are already sorted? How would that impact the approach?

FAQ

What is the best way to approach the "Construct String With Repeat Limit" problem?

The best approach is to use a greedy strategy, starting with the lexicographically largest characters and ensuring the repeatLimit constraint is respected through a heap or hash table.

How do I handle characters that appear more than repeatLimit times?

When a character appears more than the allowed repeatLimit, adjust the number of repetitions or skip to the next valid character, ensuring the result remains valid.

What is the time complexity of this problem?

The time complexity is O(N * log K), where N is the length of the string and K is the number of unique characters in the string.

What makes the solution greedy?

The solution is greedy because it always picks the lexicographically largest available character while ensuring the repeatLimit constraint is met.

Can you explain the use of the heap in this problem?

The heap is used to efficiently select the largest character available for string construction. It ensures that at each step, we can quickly access the next valid character to append.

terminal

Solution

Solution 1: Greedy Algorithm

First, we use an array $cnt$ of length $26$ to count the number of occurrences of each character in string $s$. Then, we enumerate the $i$th letter of the alphabet in descending order, each time taking out at most $\min(cnt[i], repeatLimit)$ of letter $i$. If after taking them out $cnt[i]$ is still greater than $0$, we continue to take the $j$th letter of the alphabet, where $j$ is the largest index satisfying $j < i$ and $cnt[j] > 0$, until all letters are taken.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

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)

Continue Practicing

#3081 replace question marks in string to minimize its value #2131 longest palindrome by concatenating two letter words #2384 largest palindromic number