LeetCode Entry
763. Partition Labels
Split string into separate chars sets
763. Partition Labels medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/943
Problem TLDR
Split string into separate chars sets #medium
Intuition
Look at the last index of the char, split when maximum of the last is current.
Approach
- can you do it one-pass?
- Golf: Kotlin - associate, Rust - chunked_by
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\) or O(result)
Code
fun partitionLabels(s: String) = buildList<Int> {
var l = -1; var r = 0; val e = s.indices.associate { s[it] to it }
for (i in s.indices) {
r = max(r, e[s[i]]!!); if (i == r) { add(r - l); l = i }
}
}
fun partitionLabels(s: String) = buildList<Int> {
val b = IntArray(26) { -1 }
for ((i, c) in s.withIndex()) {
if (b[c - 'a'] < 0) { b[c - 'a'] = size; this += 0 }
while (b[c - 'a'] < size - 1) {
this[size - 2] += removeLast()
for (k in 0..25) if (b[k] == size) b[k]--
}
this[size - 1]++
}
}
pub fn partition_labels(s: String) -> Vec<i32> {
let (mut s, mut e, mut r, mut l) = (s.as_bytes(), vec![0; 26], 0, 0);
for i in 0..s.len() { e[(s[i] - b'a') as usize] = i }
s.chunk_by(|&c, _| { l += 1; r = r.max(e[(c - b'a') as usize]); l <= r })
.map(|ch| ch.len() as _).collect()
}
vector<int> partitionLabels(string s) {
int e[26]; for (int i = 0; i < size(s); ++i) e[s[i] - 'a'] = i;
vector<int> res;
for (int i = 0, r = 0, l = -1; i < size(s); ++i)
if ((r = max(r, e[s[i] - 'a'])) == i) res.push_back(r - l), l = i;
return res;
}