{x}
blog image

Construct String With Repeat Limit

You are given a string s and an integer repeatLimit. Construct a new string repeatLimitedString using the characters of s such that no letter appears more than repeatLimit times in a row. You do not have to use all characters from s.

Return the lexicographically largest repeatLimitedString possible.

A string a is lexicographically larger than a string b if in the first position where a and b differ, string a has a letter that appears later in the alphabet than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the longer string is the lexicographically larger one.

 

Example 1:

Input: s = "cczazcc", repeatLimit = 3
Output: "zzcccac"
Explanation: 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"
Explanation: 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 Explanation: Construct String With Repeat Limit

This problem asks to construct the lexicographically largest string from a given string s with the constraint that no character can repeat more than repeatLimit times consecutively. The solution employs a greedy approach leveraging a frequency count and a priority (implicit, via iteration order) to achieve this.

Approach

  1. Frequency Count: First, we count the occurrences of each character (a-z) in the input string s using a frequency array cnt (or hash map).

  2. Greedy Construction: We iterate through the characters in reverse lexicographical order (z to a). For each character:

    • We append as many instances of that character as possible (up to repeatLimit) to the result string ans. We update the character's count in cnt.

    • If we've used all occurrences of the current character, we move to the next character.

    • If we haven't used all occurrences of the current character and we've reached the repeatLimit, we need to find the next lexicographically smaller character that still has occurrences available. We append one instance of that character, update its count, and continue the process. This ensures we're always using the largest possible characters while respecting the repeat limit.

  3. Return Result: Finally, we return the constructed string ans.

Time and Space Complexity

  • Time Complexity: O(N + 26), where N is the length of the input string s. The dominant operations are iterating through s to count frequencies (O(N)) and then iterating through the alphabet (O(26)), building the resulting string. The 26 is a constant, so it's essentially linear time.

  • Space Complexity: O(26), to store the frequency array cnt. This space is constant and doesn't depend on the input size.

Code Implementation (Python)

class Solution:
    def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
        cnt = [0] * 26
        for char in s:
            cnt[ord(char) - ord('a')] += 1
 
        ans = []
        j = 24  # Index for the next smallest character
        for i in range(25, -1, -1): # Iterate from 'z' to 'a'
            j = min(i - 1, j)  # Ensure j is always less than or equal to i-1
            while True:
                x = min(repeatLimit, cnt[i])
                cnt[i] -= x
                ans.extend([chr(ord('a') + i)] * x)  #Efficient append using extend
 
                if cnt[i] == 0:
                    break
 
                while j >= 0 and cnt[j] == 0:
                    j -= 1
                if j < 0:
                    break
 
                cnt[j] -= 1
                ans.append(chr(ord('a') + j))
 
        return "".join(ans)

The code in other languages (Java, C++, Go, TypeScript) follows a very similar structure and logic, just adapting the syntax and data structures of each language. The core algorithm remains the same greedy approach.