Given a string s and an integer k, return true if you can use all the characters in s to construct k palindrome strings or false otherwise.

&nbsp;
Example 1:

Input: s = "annabelle", k = 2
Output: true
Explanation: You can construct two palindromes using all characters in s.
Some possible constructions "anna" + "elble", "anbna" + "elle", "anellena" + "b"


Example 2:

Input: s = "leetcode", k = 3
Output: false
Explanation: It is impossible to construct 3 palindromes using all the characters of s.


Example 3:

Input: s = "true", k = 4
Output: true
Explanation: The only possible solution is to put each character in a separate string.


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 105
	s consists of lowercase English letters.
	1 &lt;= k &lt;= 105


from collections import Counter

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if k > len(s):
            return False
        h = Counter(s)
        countOdd = 0
        for value in h.values():
            if value % 2:
                countOdd += 1
        if countOdd > k:
            return False
        return True
class Solution {
    public boolean canConstruct(String s, int k) {
        if(k==s.length())
        {
            return true;
        }
        else if(k>s.length())
        {
            return false;
        }
        Map<Character,Integer> map=new HashMap<Character,Integer>();
        for(int i=0;i<s.length();i++)
        {
            if(map.containsKey(s.charAt(i)))
            {
                int count=map.get(s.charAt(i));
                map.put(s.charAt(i),count+1);
            }
            else
            {
                map.put(s.charAt(i),1);
            }
        }
        int odd=0;
        for(Map.Entry<Character,Integer>ele:map.entrySet())
        {
            if((ele.getValue()%2)==1)
            {
                odd++;
            }
        }
        return (odd<=k);
    }
}
class Solution {
public:
    bool canConstruct(string s, int k) {
        if(s.size() < k) return false;
        
        unordered_map<char, int> m;
        for(char c : s) m[c]++;
        
        int oddFr = 0;
        for(auto i : m) if(i.second % 2) oddFr++;
        
        return oddFr <= k;
    }
};
var canConstruct = function(s, k) {
    if(s.length < k) return false;
    // all even all even
    // all even max k odd
    const freq = {};
    for(let c of s) {
        freq[c] = (freq[c] || 0) + 1;
    }

    let oddCount = 0;
    const freqOfNums = Object.values(freq);
    for(let cnt of freqOfNums) {
        if(cnt & 1) oddCount++;
    }

    return oddCount <= k;
};
Construct K Palindrome Strings