Problem Statement
Count Odd Approach
class Solution:
def canConstruct(self, s: str, k: int) -> bool:
counter = Counter(s)
counts = counter.values()
N = len(s)
if N < k:
return False
odd = sum(1 for count in counts if count % 2 != 0)
return False if odd > k else True
Editorial
Approach 1: Count Odd Frequencies
class Solution:
def canConstruct(self, s: str, k: int) -> bool:
# Handle edge cases
if len(s) < k:
return False
if len(s) == k:
return True
# Initialize frequency dictionary and odd_count
freq = [0] * 26
odd_count = 0
# Increment the value of the index corresponding to the current character
for char in s:
freq[ord(char) - ord("a")] += 1
# Count the number of characters that appear an odd number of times in s
for count in freq:
if count % 2 == 1:
odd_count += 1
# Return if the number of odd frequencies is less than or equal to k
return odd_count <= k
Approach 2: Bit Manipulation
class Solution:
def canConstruct(self, s: str, k: int) -> bool:
# Handle edge cases
if len(s) < k:
return False
if len(s) == k:
return True
# Initialize oddCount as an integer bitmask
odd_count = 0
# Update the bitmask for each character in the string
for chr in s:
odd_count ^= 1 << (ord(chr) - ord("a"))
# Return if the number of odd frequencies is less than or equal to
return bin(odd_count).count("1") <= k
