C++ solution based on pidgeonhole principle
If we have more odd frequency characters than palindromes, then at least 2 odd frequency characters must be in the same palindrome. Since this is not possible, 
If we have more odd frequency characters than palindromes, then at least 2 odd frequency characters must be in the same palindrome. Since this is not possible, we return true if we have fewer or equal to k odd frequency characters.\n\n```\nclass Solution {\npublic:\n    bool canConstruct(string s, int k) {\n        if (s.size() < k) return false;\n        \n        vector<int> count(26, 0);\n        for (char c: s)\n            count[c-\'a\']++;\n        \n        int countOdd = count_if(count.begin(), count.end(), [](int i) {\n            return i % 2;\n        });\n        \n        // Pidgeonhole, 2 odd freq chars must be in a palindrome, which is impossible        \n        return countOdd <= k;\n    }\n};\n```
[]