LeetCode Entry
3223. Minimum Length of String After Operations
Length after removing repeatings > 2
3223. Minimum Length of String After Operations medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/863
Problem TLDR
Length after removing repeatings > 2 #medium
Intuition
The takeaways are always either 1 or 2:
// 1 -> 1
// 2 -> 2
// 3 -> 1
// 4 -> 2
// 5 -> 3 -> 1
// 6 -> 4 -> 2
// 7 -> 1
// 8 -> 2
Count each char’s frequency.
Approach
- we can do some arithmetics
2 - 2 * f - careful: only count existing characters
- we can apply bitmasks instead of
f[26]
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun minimumLength(s: String) =
s.groupBy { it }.values.sumBy {
2 - it.size % 2
}
pub fn minimum_length(s: String) -> i32 {
let mut f = vec![0; 26];
for b in s.bytes() { f[(b - b'a') as usize] += 1 }
(0..26).filter(|&b| f[b] > 0).map(|b| 2 - f[b] % 2).sum()
}
int minimumLength(string s) {
int e = 0, f = 0;
for (char c: s)
f ^= 1 << (c - 'a'), e |= 1 << (c - 'a');
return 2 * __builtin_popcount(e) - __builtin_popcount(f & e);
}