Leetcode 1400: Construct K Palindrome Strings

 https://leetcode.com/problems/construct-k-palindrome-strings/description/

Notes:

This question seems not easy, but actually is not.

We just need to use one property of palindrome: at most there is one letter with odd count.

Thus, in order to form k palindromes, at most we have k letters with odd count.

If the size of string is smaller than k, there is no way to form k palindrome.

See the code below:

class Solution {
public:
    bool canConstruct(string s, int k) {
        int n = s.size(), res = 0;
        if(n<k) return false;
        if(n==k) return true;
        vector<int> ct(26, 0);
        for(auto &a : s) ++ct[a-'a'];
        for(auto &a : ct) {
            if(a & 1) ++res;
        }
        return res <= k;
    }
};