2182. Construct String With Repeat Limit

MediumGreedyStringCountingHeap (Priority Queue)
Leetcode Link

Problem Description

You are provided with a string s and an integer repeatLimit. The task is to create a new string, called repeatLimitedString, using the characters from s. The catch is that no character can repeat more than repeatLimit times consecutively. It is not necessary to use all characters from s. The goal is to build the lexicographically largest repeatLimitedString possible.

A string is considered lexicographically larger if at the position where two strings start to differ, the string with the character higher in the alphabet comes first. If they are identical up to the length of the shorter one, then the longer string is considered larger.

Intuition

To form the lexicographically largest string, we should always prefer to use the largest character available (closest to 'z'). We start from the end of the alphabet and move towards the start ('z' to 'a'), using up to repeatLimit occurrences of the current character before we must use a different character to avoid breaking the repeat rule.

The intuition behind the solution is as follows:

  • Count the occurrences of each character in the input string s. This is done to quickly find out how many times we can use each character without counting repeatedly.
  • Start constructing the repeatLimitedString by iterating from the highest character ('z') down to the lowest ('a'). Add up to repeatLimit instances of the current character to the result.
  • If there are still occurrences of the current character left (more than repeatLimit), add a character next in line (the highest character remaining that is not the current one). This step ensures that we do not break the repeat limit for the current character.
  • Repeat the process of adding the current character (up to the repeatLimit) and then the next in line (just once) until we run out of characters or we can no longer add the current character without breaking the repeat limit.
  • If we reach a point where no other characters are available to be inserted between repeats of the current character, we terminate the process as we can't add more of the current character than allowed.
  • By following this process and prioritizing the largest character possible at each step, we ensure that the result is the lexicographically largest possible string under the given constraints.

Learn more about Greedy and Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The solution approach involves a few key steps and makes use of a frequency counter and a greedy strategy to construct the required repeatLimitedString.

Here's a step-by-step walkthrough of the implementation:

  1. Counting Frequencies: We use an array cnt of size 26 (since there are 26 letters in the English alphabet) to count the occurrences of each character in string s. The ASCII value is used to map characters 'a' to 'z' to indices 0 to 25.

  2. Iterating in Reverse: We loop through the cnt array in reverse order starting from the index corresponding to 'z' (25) down to 'a' (0). This allows us to consider characters in decreasing lexicographic order.

  3. Adding Characters to the Result: In each iteration, we add up to repeatLimit instances of the character corresponding to the current index to the answer list ans, decrementing the count in cnt. The character to be added is obtained by computing chr(ord('a') + i), where i is the current index.

  4. Maintaining the Repeat Limit: If the count of the current character is not exhausted after adding repeatLimit instances, we need to add a different character to ensure no character is repeated more than repeatLimit times in a row.

  5. Finding the Next Character: We use another pointer j and decrement it to find the next available character with a nonzero count. We then add one instance of this character to ans, ensuring the repeat limit condition is satisfied.

  6. Stopping Conditions: There are two stopping conditions in the while loop. The loop ends when the count of the current character reaches 0 (cnt[i] == 0), or when there is no other character left to insert (j < 0).

By combining the usage of the frequency counter with a greedy approach, we ensure that we always construct the string with the highest lexicographical order possible under the given constraints of the repeatLimit.

Here's a portion of the code that visualizes this process:

1for i in range(25, -1, -1):
2    j = i - 1
3    while True:
4        for _ in range(min(repeatLimit, cnt[i])):
5            cnt[i] -= 1
6            ans.append(chr(ord('a') + i))
7        if cnt[i] == 0:
8            break
9        while j >= 0 and cnt[j] == 0:
10            j -= 1
11        if j < 0:
12            break
13        cnt[j] -= 1
14        ans.append(chr(ord('a') + j))
15return ''.join(ans)

In the above code, ans is a list that eventually contains the characters of the repeatLimitedString in the desired order. The join method is used to combine these characters into a string before returning it as the final answer.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these properties could exist for a graph but not a tree?

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose we have the string s = "aabab" and a repeatLimit of 2. We want to construct the lexicographically largest repeatLimitedString by using the characters from s according to the given constraints.

  1. Counting Frequencies:

    • We count each character's frequency and store it in an array cnt. Here's what the cnt array will look like for each alphabet character:
      • 'a': 3
      • 'b': 2
    • The other characters are not present in s and would have a count of 0.

  2. Iterating in Reverse:

    • We start from 'z' and go down to 'a', so the first character we consider from s that has a non-zero frequency is 'b'.

  3. Adding Characters to the Result:

    • We add 'b' to our result. Since repeatLimit is 2 and we have 2 'b's, we add both of them: repeatLimitedString = "bb".
    • We decrement the count of 'b' in cnt to 0.

  4. Maintaining the Repeat Limit:

    • Now that we've used all 'b's, we move to the next available character with the highest lexicographical value, which is 'a'.
    • We can add up to 2 'a's (due to repeatLimit) to repeatLimitedString which now becomes: repeatLimitedString = "bbaa".

  5. Finding the Next Character:

    • We have one 'a' remaining, but we cannot add it immediately because that would violate the repeatLimit.
    • We search for the next available character, but as we've used up all 'b's, and no characters are left, we're only left with 'a'.

  6. Stopping Conditions:

    • We've reached the stopping condition because we have no characters left that we can insert to avoid having more than 2 consecutive 'a's.
    • Thus, we cannot add the last 'a'.

The lexicographically largest repeatLimitedString we can create with the given s and repeatLimit is bbaa.

By following the described solution approach, we constructed the lexicographically largest string without breaking the rules of the given constraints.

Solution Implementation

1class Solution:
2    def repeatLimitedString(self, s: str, repeat_limit: int) -> str:
3        # Initialize a list to keep track of the count of each character
4        char_count = [0] * 26
5      
6        # Count the occurrences of each character in the input string s
7        for c in s:
8            char_count[ord(c) - ord('a')] += 1
9      
10        # Initialize a list to build the answer string
11        answer = []
12      
13        # Iterate over characters from 'z' to 'a'
14        for i in range(25, -1, -1):
15            # Find the next character to place if we hit the repeat limit
16            next_char_index = i - 1
17          
18            # Keep placing characters until we run out
19            while True:
20                # Place the current character (up to the repeat limit) in the answer
21                for _ in range(min(repeat_limit, char_count[i])):
22                    char_count[i] -= 1
23                    answer.append(chr(ord('a') + i))
24              
25                # If we have placed all instances of the current character, move to the next
26                if char_count[i] == 0:
27                    break
28              
29                # Find the next highest character which we haven't exhausted
30                while next_char_index >= 0 and char_count[next_char_index] == 0:
31                    next_char_index -= 1
32              
33                # If there are no more characters to use, we are done
34                if next_char_index < 0:
35                    break
36              
37                # Place the next character
38                char_count[next_char_index] -= 1
39                answer.append(chr(ord('a') + next_char_index))
40      
41        # Return the constructed string
42        return ''.join(answer)
43
1class Solution {
2
3    public String repeatLimitedString(String s, int repeatLimit) {
4        // Array to hold the count of each letter in the string
5        int[] letterCount = new int[26];
6
7        // Counting the occurrences of each character in the string
8        for (char ch : s.toCharArray()) {
9            letterCount[ch - 'a']++;
10        }
11
12        // StringBuilder to build the result string
13        StringBuilder result = new StringBuilder();
14
15        // Iterate from the letter 'z' to 'a'
16        for (int i = 25; i >= 0; --i) {
17            // Pointer to check for the next available smaller character
18            int nextCharIndex = i - 1;
19
20            while (true) {
21                // Append the current character up to repeatLimit times
22                for (int k = Math.min(repeatLimit, letterCount[i]); k > 0; --k) {
23                    letterCount[i]--; // Decrement the count of the current character
24                    result.append((char) ('a' + i)); // Add the current character to the result
25                }
26
27                // If all occurrences of the current character have been used up, break out of the loop
28                if (letterCount[i] == 0) {
29                    break;
30                }
31
32                // Find the next available character which has at least one occurrence left
33                while (nextCharIndex >= 0 && letterCount[nextCharIndex] == 0) {
34                    --nextCharIndex;
35                }
36
37                // If there are no more characters left to use, break out of the loop
38                if (nextCharIndex < 0) {
39                    break;
40                }
41
42                // Append the next available character
43                letterCount[nextCharIndex]--;
44                result.append((char) ('a' + nextCharIndex));
45            }
46        }
47
48        // Return the result as a string
49        return result.toString();
50    }
51}
52
1class Solution {
2public:
3    string repeatLimitedString(string s, int repeatLimit) {
4        // Count occurrences of each character in the input string
5        vector<int> charCounts(26, 0);
6        for (char ch : s) {
7            charCounts[ch - 'a']++;
8        }
9
10        // Initialize the answer string
11        string result;
12
13        // Iterate over the characters starting from 'z' to 'a'
14        for (int i = 25; i >= 0; --i) {
15            int nextCharIndex = i - 1;
16
17            // Continue to construct the string until all chars are used
18            while (true) {
19                // Add the current character up to repeatLimit times
20                int repeatCount = min(charCounts[i], repeatLimit);
21                for (int k = repeatCount; k > 0; --k) {
22                    charCounts[i]--;
23                    result.push_back('a' + i);
24                }
25
26                // Break the loop if this character is fully used
27                if (charCounts[i] == 0) break;
28
29                // Find the next available character with remaining count
30                while (nextCharIndex >= 0 && charCounts[nextCharIndex] == 0) {
31                    --nextCharIndex;
32                }
33              
34                // Break if there are no more characters to use
35                if (nextCharIndex < 0) break;
36
37                // Add the next available character to the result string
38                charCounts[nextCharIndex]--;
39                result.push_back('a' + nextCharIndex);
40            }
41        }
42
43        // Return the constructed string
44        return result;
45    }
46};
47
1function repeatLimitedString(s: string, repeatLimit: number): string {
2    // Count occurrences of each character in the input string
3    const charCounts: number[] = new Array(26).fill(0);
4    for (const ch of s) {
5        charCounts[ch.charCodeAt(0) - 'a'.charCodeAt(0)]++;
6    }
7
8    // Initialize the answer string
9    let result: string = '';
10
11    // Iterate over the characters starting from 'z' to 'a'
12    for (let i = 25; i >= 0; --i) {
13        let nextCharIndex = i - 1;
14
15        // Continue to construct the string until all chars are used
16        while (true) {
17            // Add the current character up to repeatLimit times
18            const repeatCount = Math.min(charCounts[i], repeatLimit);
19            for (let k = repeatCount; k > 0; --k) {
20                charCounts[i]--;
21                result += String.fromCharCode('a'.charCodeAt(0) + i);
22            }
23
24            // Break the loop if this character is fully used
25            if (charCounts[i] === 0) break;
26
27            // Find the next available character with remaining count
28            while (nextCharIndex >= 0 && charCounts[nextCharIndex] === 0) {
29                --nextCharIndex;
30            }
31          
32            // Break if there are no more characters to use
33            if (nextCharIndex < 0) break;
34
35            // Add the next available character to the result string
36            charCounts[nextCharIndex]--;
37            result += String.fromCharCode('a'.charCodeAt(0) + nextCharIndex);
38        }
39    }
40
41    // Return the constructed string
42    return result;
43}
44
Not Sure What to Study? Take the 2-min Quiz：

Which of these properties could exist for a graph but not a tree?

Time and Space Complexity

Time Complexity

The time complexity of the code can be broken down into the following major parts:

  1. Character Counting: The first loop counts the frequency of each character in the string s. This loop runs exactly len(s) times. Therefore, this part has a time complexity of O(n) where n is the length of the string s.

  2. Main Loop for Building the Answer: The outer loop runs 26 times (once for each lowercase English letter). The inner loop could, in the worst case, run roughly n / repeatLimit times if all characters are the same and need to be interspersed with another character after hitting the repeatLimit. However, since we only insert a single character in between repetitions and then continue with the same character until the repeatLimit is hit again, the actual number of visits to each character count (cnt[i]) will be proportional to its frequency. This means that the operation count is effectively linear with respect to the string length n. Therefore, we can consider this part also to have a time complexity of O(n).

  3. Looking for the Next Character: Within the inner while loop, there's another loop that searches for the next available character (j) if the repeat limit is reached. In the worst-case scenario, this could traverse all characters smaller than i, adding an extra factor of at most 26 (constant time) per repeat limit hit. Thus, this does not affect the overall linear complexity relative to n.

Hence the total time complexity is O(n) since the character search is bounded by a constant and doesn't depend on n.

Space Complexity

The space complexity is determined by the additional space used by the algorithm which is not part of the input or output:

  1. Character Count Array: The cnt array has a space complexity of O(1) since it is always a fixed size of 26 regardless of the input size.

  2. Output List: The ans list ultimately stores each character from the input string in some order, and hence it will have a space complexity of O(n).

Thus, the total space complexity of the algorithm is O(n) due to the output list size being proportional to the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Heap Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫