1400: Construct-K-Palindrome-Strings
Medium
This question is a bit of a troll.
The trick to this question is to realise that the
minimum number of palindromes is equal to the
number of letters that have an
odd count in s and the
maximum number of palindromes is equal to
s.size() (since every letter itself is a
palindrome).
Therefore, we just need to check that k lies
between the minimimum* and *maximum** count.
Code:
class Solution {
public:
bool canConstruct(string s, int k) {
vector<int> alphabet (26, 0);
for (char &c : s) {
alphabet[c-'a'] ^= 1;
}
int odd = 0;
for (int i = 0; i < 26; ++i) {
odd += alphabet[i];
}
return (k >= odd) && (k <= s.size());
}
};