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 <= 105s consists of lowercase English letters.This approach involves maintaining a frequency count of each character in the input string. We can then iterate over the characters in reverse lexicographical order, attempting to add each character to the result while respecting the repeatLimit. If the repeat limit is reached for a character, we temporarily insert the next available smaller character to break the sequence. We continue this process until all valid characters have been used.
The solution involves counting the frequency of each character in the input string. We then iterate from 'z' to 'a', adding as many of the current character as the repeat limit allows, before adding the next highest available character to break any excessive repetition. This continues until all characters are used according to the rules.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m), where n is the length of the string and m = 26, the number of letters in the alphabet.
Space Complexity: O(1), as the frequency array size is fixed.
Construct String With Repeat Limit - Leetcode 2182 - Python • NeetCodeIO • 5,554 views views
Watch 9 more video solutions →Practice Construct String With Repeat Limit with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor