The main difficulty is to define how chars frequencies can be used to make k palindromes:
chars number must be at least k, this is a lower boundary
the odd frequencies count must be <= k, this is a higher boundary
even frequencies are all dissolved into any number of palindromes
Approach
to find those rules on the fly, we should do attempts on examples (by running the code, or writing them down, or imagine if you can)
Complexity
Time complexity: $$O(n)$$
Space complexity: $$O(1)$$, O(n) for Kotlin golf
Code
fun canConstruct(s: String, k: Int) =
k <= s.length && s.groupBy { it }
.values.sumBy { it.size % 2 } <= k
pub fn can_construct(s: String, k: i32) -> bool {
let (mut f, k) = (vec![0; 26], k as usize);
for b in s.bytes() { f[(b - b'a') as usize] += 1 }
k <= s.len() &&
(0..26).map(|b| f[b] % 2).sum::<usize>() <= k
}
bool canConstruct(string s, int k) {
int f[26] = {0}, c = 0;
for (int i = 0; i < s.size(); ++i) c += 2 * (++f[s[i] - 'a'] % 2) - 1;
return k <= s.size() && c <= k;
}
Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.
