✅100% || C++ || Python || 🎈Hash Table || ✨Bit-Set  || 🚀Beginner-Friendly
IntuitionThe main idea is to count the number of characters with odd frequencies in the string s. A palindrome can have at most one character with an odd freque
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The main idea is to count the number of characters with odd frequencies in the string `s`. A palindrome can have at most one character with an odd frequency (this would be the middle character in case of odd-length palindromes). Therefore, if the number of characters with odd frequencies (`odd`) is less than or equal to `k`, we can construct `k` palindrome strings.
# Approach 1: Using unordered_map
- Count Character Frequencies: Using an unordered_map, count the frequency of each character in the string `s`. 

- Odd Count Characters: Count how many of these characters have an odd frequency.
- Check Constructibility: Compare the count of odd frequency characters to `k`. If `odd` ≤ `k` and the length of `s` is at least `k`, return true. Otherwise, return false.

# Approach 2: Using bitset (Optimized)
- Use bitset for Frequencies: Using a bitset to keep track of odd frequencies of characters. Every time a character appears, flip its corresponding bit.

- Odd Count Characters: The number of set bits in the bitset will give the count of characters with odd frequencies.

- Check Constructibility: Compare the count of odd frequency characters to `k`. If `odd`≤ `𝑘` and the length of `𝑠` is at least `𝑘`, return true. Otherwise, return false.
<!-- Describe your approach to solving the problem. -->

# Complexity

**Approach 1: unordered_map**
- Time Complexity: $$O(n)$$, where `𝑛` is the length of the string `𝑠`.

- Space Complexity: $$O(n)$$.

**Approach 2: bitset**
- Time Complexity: $$O(n)$$.

- Space Complexity: $$O(1)$$ (more optimized).

# Code
```cpp []
class Solution {
public:
    bool canConstruct(string s, int k) {
        if (s.length() < k) return false; 
        unordered_map<char, int> freq; 
        for (char c : s) { freq[c]++; } 
        int odd = 0; 
        for (auto& pair : freq) 
            if (pair.second % 2 != 0) 
                odd++;
        return odd <= k;
    }
};
```
```python []
from collections import Counter
class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if len(s) < k: 
            return False 
        freq = Counter(s) 
        odd = sum(1 for count in freq.values() if count % 2 != 0) 
        return odd <= k
```
#
```cpp []
class Solution {
public:
    bool canConstruct(string s, int k) {
        bitset<26>odd;
        for(char& c:s)
            odd.flip(c-'a');
        return odd.count()<=k && k<=s.length();
    }
};
```
```python []
class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if len(s) < k: 
            return False 
        odd = set() 
        for c in s: 
            if c in odd: 
                odd.remove(c)
            else: 
                odd.add(c) 
        return len(odd) <= k
```
['Hash Table', 'String', 'Greedy', 'Counting', 'C++', 'Python3']