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

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Mathematics

Greedy algorithms

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
		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


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


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 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:
		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:
		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
		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 = 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:
		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:
		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:
		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


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


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)