Construct K Palindrome Strings

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());
    }
};

complexity

• Time: O(n)
• Size: O(1)