Given a string s and an integer k. You should construct k non-empty palindrome strings using all the characters in s.
Return True if you can use all the characters in s to construct k palindrome strings or False otherwise.
 
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.

Example 4:
Input: s = "yzyzyzyzyzyzyzy", k = 2
Output: true
Explanation: Simply you can put all z's in one string and all y's in the other string. Both strings will be palindrome.

Example 5:
Input: s = "cr", k = 7
Output: false
Explanation: We don't have enough characters in s to construct 7 palindromes.

 
Constraints:

1 <= s.length <= 10^5
All characters in s are lower-case English letters.
1 <= k <= 10^5

Difficulty: interview

Starter code:

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        

Solutions:
from collections import Counter
class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if k > len(s): #return False
            return False
        counter = Counter(s)
        odd_counts = 0
        
        for char in counter:
            if counter[char] % 2 == 1:
                odd_counts += 1
        
        return odd_counts <= k

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        from collections import Counter
        if len(s) < k:
            return False
        oc = 0
        for _ , val in list(Counter(s).items()):
            if val % 2 == 1:
                oc += 1
        return False if oc > k else True
        # return False if k < len([1 for _ , val in Counter(s).items() if val % 2 == 1]) else True


class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
          n = len(s)
          if n < k:
            return False
          if n == k:
            return True

          ch_to_cnt = collections.defaultdict(int)
          for ch in s:
            ch_to_cnt[ch] += 1

          for cnt in ch_to_cnt.values():
            if cnt %2 == 1:
              k -= 1
          return k >= 0

from collections import defaultdict

class Solution:
    
    def canConstruct(self, s: str, k: int) -> bool:
        d = defaultdict(int)
        if len(s) < k:
            return False
        
        for char in s:
            d[char] += 1
            
        odd = 0
        for key in d:
            print(key)
            if d[key] % 2 != 0:
                
                odd += 1
        
        return odd <= k


from collections import defaultdict

class Solution:
    
    def canConstruct(self, s: str, k: int) -> bool:
        d = defaultdict(int)
        if len(s) < k:
            return False
        
        for char in s:
            d[char] += 1
            
        odd = 0
        for key in d:
            if d[key] % 2 != 0:
                
                odd += 1
        
        return odd <= k


class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        c = Counter(s)
        return sum(c.values()) >= k and len([v for v in c.values() if v % 2]) <= k

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if len(s) < k:
            return False
        numodds = 0
        keys = collections.defaultdict(int)
        for c in s:
            keys[c] += 1
        
        for key in keys:
            if keys[key] % 2:
                numodds += 1
        
        return numodds <= k

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if k > len(s):
            return False
        dictionary = {}
        for character in s:
            if character in dictionary:
                dictionary[character] += 1
            else:
                dictionary[character] = 1
        odd_occurences = 0
        for e in list(dictionary.values()):
            odd_occurences += e % 2
        if odd_occurences > k:
            return False
        return True
        


class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if k > len(s):
            return False
        dictionary = {}
        for character in s:
            if character in dictionary:
                dictionary[character] += 1
            else:
                dictionary[character] = 1
        odd_occurences = 0
        for e in dictionary.values():
            odd_occurences += e % 2
        if odd_occurences > k:
            return False
        return True

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if k > len(s):
            return False
        dictionary = {}
        for character in s:
            if character in dictionary:
                dictionary[character] += 1
            else:
                dictionary[character] = 1
        print((list(dictionary.values())))
        odd_occurences = 0
        for e in list(dictionary.values()):
            if e % 2 == 1:
                odd_occurences += 1
        print(odd_occurences)
        if odd_occurences > k:
            return False
        return True
        


class Solution:
    
    def is_palindrome(self, s):
        return bool(s == s[::-1])        
    
    def canConstruct(self, s: str, k: int) -> bool:
        r_map = dict()
        if k > len(s):
            return False
        for x in s:
            if x not in r_map:
                r_map[x] = 1
            else:
                r_map[x] += 1
        odd_count = 0
        for key in r_map:
            if r_map[key] % 2 == 1:
                odd_count += 1
        return odd_count <= k

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        dict = {}
        for c in s:
            if c in dict: dict[c] += 1
            else: dict[c] = 1
        num_of_distinct = 0
        for key in dict.keys():
            if dict[key]%2 == 1: num_of_distinct += 1
        return num_of_distinct <= k and k <= len(s)

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if k > len(s):
            return False
        if k == len(s):
            return True
        charCount = Counter(s)
        countOdd = 0
        for count in list(charCount.values()):
            if count % 2 != 0:
                countOdd += 1
        return countOdd <= k


class Solution:    
    def canConstruct(self, s: str, k: int) -> bool:
        r_map = dict()
        if k > len(s):
            return False
        for x in s:
            if x not in r_map:
                r_map[x] = 1
            else:
                r_map[x] += 1
        odd_count = 0
        for key in r_map:
            if r_map[key] % 2 == 1:
                odd_count += 1
        return odd_count <= k

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if len(s) < k:
            return False
        
        d = {}
        for c in list(s):
            if c in d:
                d[c] += 1
            else:
                d[c] = 1
            
        print(d)
        
        if len(list(d.keys())) == k:
            return True
        else:
            odds = 0
            for v in list(d.values()):
                if v % 2 == 1:
                    odds += 1
                    
            return False if odds > k else True


class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        
        # return sum(i & 1 for i in collections.Counter(s).values()) <= k <= len(s)
    
#         if len(s) < k: return False
#         seen = {}
#         odd = 0
#         for char in s:
#             seen[char] = seen.get(char, 0) + 1
        
#         for val in seen.values():
#             if val % 2 == 1:
#                 odd += 1
        
#         if odd > k: return False
#         return True
        
        
        if len(s) < k: 
            return False
        
        seen = {}
        odd = 0
        
        for letter in s:
            seen[letter] = seen.get(letter, 0) + 1
        
        for value in seen.values():
            if value % 2 != 0:
                odd += 1
        
        if odd > k:
            return False
        
        return True

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        count = {}
        for char in s:
            count[char] = count.get(char,0)+1
#        print(len([char for char in count if count[char]%2==1]), count)
        return k>=len([char for char in count if count[char]%2==1]) and k<=len(s)

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        
        if len(s)<k:
            return False
        
        dic={}
        for sym in s:
            if sym in dic.keys():
                dic[sym]=1-dic[sym]
            else:
                dic[sym]=1

        #num=sum(dic.values())
        num=0
        for i in dic.values():
            num+=i
        
        if num<=k:
            return True
        else:
            return False

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        d = {}
        for i in range(len(s)):
            if s[i] in d:
                d[s[i]] += 1
            else:
                d[s[i]] = 1
                
        odds = 0
        for v in d.values():
            if v % 2 == 1:
                odds += 1
        return odds <= k and k <= len(s)

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        return sum(i &1 for i in collections.Counter(s).values()) <= k <= len(s)

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        d = {}
        for i in range(len(s)):
            if s[i] in d:
                d[s[i]] += 1
            else:
                d[s[i]] = 1
        odds = 0
        for v in d.values():
            if v % 2 == 1:
                odds += 1
        return odds <= k and k <= len(s) 

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if len(s) < k:
            return False

        dict = {}
        for st in s:
            if st in dict:
                dict[st] += 1
            else:
                dict[st] = 1

        countOddCh = 0
        for key, v in dict.items():
            if v % 2 != 0:
                countOddCh += 1

        if countOddCh > k:
            return False

        return True

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if k > len(s):
            return False
        
        char_cnt = defaultdict(int)
        for char in s:
            char_cnt[char] += 1
        
        odd_cnt = 0
        for char, cnt in char_cnt.items():
            if cnt % 2 == 1:
                odd_cnt += 1
                if odd_cnt > k:
                    return False
        
        return True

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if k > len(s):
            return False
        
        cnt = Counter()
        
        for c in s:
            cnt[c] +=1
        
        
        single_nums = 0
        
        for key in cnt:
            if cnt[key] % 2 == 1:
                single_nums +=1
        
        if k < single_nums:
            return False
        
        return True
            
        
        
            
        


class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        odd = 0
        counts = defaultdict(lambda: 0)
        
        for c in s:
            counts[c] += 1
            if (counts[c]%2 == 0): 
                odd -= 1
            else:
                 odd += 1
        
        if (odd > k or k>len(s)): return False
        
        return True

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        odd = 0
        counts = defaultdict(lambda: 0)
        
        for c in s:
            counts[c] += 1
            if (counts[c]%2): odd += 1
            else: odd -= 1
        
        if (odd > k or k>len(s)): return False
        
        return True

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        cnt_map = collections.defaultdict(int)
        for c in s:
            cnt_map[c] += 1
        
        n_odd = 0
        for c in cnt_map:
            if cnt_map[c] % 2 == 1:
                n_odd += 1
          
        if n_odd <= k <= len(s):
            return True
        else:
            return False


class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        '''
        Compute the frequency of each characters.
        Count the 奇数次的字母, 
        each palindrome can consume at most one char with odd                 frequency. thus k must >= |odd|.
        ans = k <= len(s) and k >= odd
        '''
        if k>len(s):
            return False
        freq=collections.defaultdict(int)
        for c in s:
            freq[c]+=1
        odd=0
        for c in freq:
            odd+=freq[c]&1
        return odd<=k

from collections import Counter
class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if len(s) < k:
            return False
        counter = Counter(s)
        count = 0
        for key in counter:
            if counter[key] % 2 == 1:
                count += 1
        return count <= k
        


class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if len(s) < k:
            return False
        cnts = collections.defaultdict(int)
        for ch in s:
            cnts[ch] += 1
        odds, evens = [], []
        for ch in cnts:
            if cnts[ch] % 2 == 1:
                odds.append(ch)
            else:
                evens.append(ch)
        return len(odds) <= k
                
                
class Solution1:
    def canConstruct(self, s: str, k: int) -> bool:
        cnts = collections.defaultdict(int)
        for ch in s:
            cnts[ch] += 1
        odds, evens = [], []
        for ch in cnts:
            if cnts[ch] % 2 == 1:
                odds.append(ch)
            else:
                evens.append(ch)
        if len(odds) > k:
            return False
        for i in range(len(odds)):
            k -= 1
            ch = odds.pop()
            cnts[ch] -= 1
            if cnts[ch] > 0:
                evens.append(ch)
        while k > len(evens):
            if not evens:
                return False
            ch = evens.pop()
            k -= 2
            cnts[ch] -= 2
            if cnts[ch] > 0:
                evens.append(ch)
        return True


class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
            if k > len(s):
                return False
            elif k == len(s):
                return True

            seen = {}

            for letter in s:
                seen[letter] = seen.get(letter, 0) + 1

            singles = 0

            for key in seen:
                value = seen[key]
                if value % 2 == 1:
                    singles += 1

            return singles <= k


class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        return sum(i & 1 for i in collections.Counter(s).values()) <= k <= len(s)        

from collections import Counter
class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        counter = Counter(s)
        evens = 0
        odds = 0
        for key, value in counter.items():
            if value % 2 == 0:
                evens += 1
            else:
                odds += 1
        return k >= odds and len(s) >= k

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        sCounter = collections.Counter(s)
        numberOfLettersWithOddCounts = len([count for count in list(sCounter.values()) if count % 2 != 0])
        
        return not (len(s) < k or numberOfLettersWithOddCounts > k)


class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        return sum(i & 1 for i in collections.Counter(s).values()) <= k <= len(s)