Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2182.html
2182. Construct String With Repeat Limit (Medium)
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 <= 105sconsists of lowercase English letters.
Similar Questions:
Solution 1. Greedy + Counting
Store frequency of characters in int cnt[26].
We pick characters in batches. In each batch, we pick the first character from z to a whose cnt is positive with the following caveats:
- If the current character is the same as the one used in the previous batch, we need to skip it.
- On top of case 1, if the
cntof the character used in the previous batch is positive, then we can only fill a single character in this batch.
-
// OJ: https://leetcode.com/problems/construct-string-with-repeat-limit/ // Time: O(N) // Space: O(1) class Solution { public: string repeatLimitedString(string s, int limit) { int cnt[26] = {}; string ans; for (char c : s) cnt[c - 'a']++; while (true) { int i = 25; bool onlyOne = false; for (; i >= 0; --i) { if (ans.size() && i == ans.back() - 'a' && cnt[i]) { // the character of our last batch still has some count left, so we only insert a single character in this batch onlyOne = true; continue; } if (cnt[i]) break; // found a character with positive count, fill with this character } if (i == -1) break; // no more characters to fill, break; int fill = onlyOne ? 1 : min(cnt[i], limit); cnt[i] -= fill; while (fill--) ans += 'a' + i; } return ans; } }; -
class Solution: def repeatLimitedString(self, s: str, repeatLimit: int) -> str: cnt = [0] * 26 for c in s: cnt[ord(c) - ord('a')] += 1 ans = [] for i in range(25, -1, -1): j = i - 1 while 1: for _ in range(min(repeatLimit, cnt[i])): cnt[i] -= 1 ans.append(chr(ord('a') + i)) 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) ############ # 2182. Construct String With Repeat Limit # https://leetcode.com/problems/construct-string-with-repeat-limit/ class Solution: def repeatLimitedString(self, s: str, repeatLimit: int) -> str: n = len(s) words = Counter(s) heap = [] res = "" last = (None, 0) for k, v in words.items(): heapq.heappush(heap, (-ord(k), v)) while len(heap) > 0: c, v = heapq.heappop(heap) c = -c if chr(c) == last[0]: count = min(repeatLimit, v) - last[1] if count <= 0: v = 0 continue v -= count res += chr(c) * count last = (chr(c), count) else: count = min(repeatLimit, v) v -= count res += chr(c) * count last = (chr(c), count) if heap and count == repeatLimit and v != 0: c2, v2 = heapq.heappop(heap) c2 = -c2 # print(chr(c), v, chr(c2), v2) res += chr(c2) * 1 v2 -= 1 if v2 > 0: heapq.heappush(heap, (-c2, v2)) last = (chr(c2), 1) if v > 0: heapq.heappush(heap, (-c, v)) return res -
class Solution { public String repeatLimitedString(String s, int repeatLimit) { int[] cnt = new int[26]; for (char c : s.toCharArray()) { cnt[c - 'a']++; } StringBuilder ans = new StringBuilder(); for (int i = 25; i >= 0; --i) { int j = i - 1; while (true) { for (int k = Math.min(repeatLimit, cnt[i]); k > 0; --k) { cnt[i]--; ans.append((char) ('a' + i)); } if (cnt[i] == 0) { break; } while (j >= 0 && cnt[j] == 0) { --j; } if (j < 0) { break; } cnt[j]--; ans.append((char) ('a' + j)); } } return ans.toString(); } } -
func repeatLimitedString(s string, repeatLimit int) string { cnt := make([]int, 26) for _, c := range s { cnt[c-'a']++ } var ans []byte for i := 25; i >= 0; i-- { j := i - 1 for { for k := min(cnt[i], repeatLimit); k > 0; k-- { cnt[i]-- ans = append(ans, 'a'+byte(i)) } if cnt[i] == 0 { break } for j >= 0 && cnt[j] == 0 { j-- } if j < 0 { break } cnt[j]-- ans = append(ans, 'a'+byte(j)) } } return string(ans) } func min(a, b int) int { if a < b { return a } return b }
Discuss
https://leetcode.com/problems/construct-string-with-repeat-limit/discuss/1784718
Note
I saw some code with the following loops
for (int i = 1; i <= 100000; ++i) {
for (int j = i; j <= 100000; j += i) {
// Some O(1) operation
}
}
The time complexity of these loops is roughly O(NlogN). Because 1/1+1/2+...+1/N is roughly logN. See https://math.stackexchange.com/questions/3367037/sum-of-1-1-2-1-3-1-n