LeetCode Entry
2182. Construct String With Repeat Limit
Max lexical ordered with repeat limit string sort
2182. Construct String With Repeat Limit medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/835
Problem TLDR
Max lexical ordered with repeat_limit string #medium #bucket_sort
Intuition
Always peek the largest value. If limit is reached peek one of the next.
Approach
- we can use a heap, but have to manage all the next chars at once
- we can use a frequency counter and two pointers: current and next
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun repeatLimitedString(s: String, repeatLimit: Int) = buildString {
val f = IntArray(26); for (c in s) f[c - 'a']++
var cnt = 0; var i = 25; var j = i
while (i >= 0) {
if (f[i] == 0) { i--; continue }
if (length == 0 || get(length - 1) == 'a' + i) cnt++ else cnt = 1
if (cnt > repeatLimit) {
j = min(j, i - 1); while (j >= 0 && f[j] == 0) j--
if (j >= 0) { append('a' + j); f[j]-- } else break
} else { append('a' + i); f[i]-- }
}
}
pub fn repeat_limited_string(s: String, repeat_limit: i32) -> String {
let mut f = [0; 26]; for b in s.bytes() { f[(b - b'a') as usize] += 1 }
let (mut cnt, mut i, mut j, mut r) = (0, 25, 25, vec![]);
loop {
if f[i] == 0 { if i == 0 { break } else { i -= 1; continue }}
if r.last().map_or(true, |&l| l == b'a' + i as u8) { cnt += 1 } else { cnt = 1 }
if cnt > repeat_limit {
if i == 0 { break } else { j = j.min(i - 1) }
loop { if j == 0 || f[j] > 0 { break } else { j -= 1 }}
if f[j] > 0 { r.push(b'a' + j as u8); f[j] -= 1 } else { break }
} else { r.push(b'a' + i as u8); f[i] -= 1}
}; String::from_utf8(r).unwrap()
}
string repeatLimitedString(string s, int repeatLimit) {
int f[26]; for (auto c: s) ++f[c - 'a'];
int cnt = 0, i = 25, j = 25, l = 26; string r;
while (i >= 0) {
if (!f[i]) { --i; continue; }
l == i ? ++cnt : cnt = 1;
if (cnt > repeatLimit) {
j = min(j, i - 1);
while (j > 0 && !f[j]) --j;
if (j >= 0 && f[j]--) { r += 'a' + j; l = j; } else break;
} else { r += 'a' + i; --f[i]; l = i; }
} return r;
}