"Checking Feasibility of Constructing  𝑘 k Palindromes from a String"
IntuitionThe problem revolves around understanding the properties of palindromes. A palindrome can have at most one character with an odd frequency. Therefore,
# Intuition
The problem revolves around understanding the properties of palindromes. A palindrome can have at most one character with an odd frequency. Therefore, to construct k palindrome strings, the minimum number of palindromes required is determined by the number of characters with odd frequencies. If k is less than this number, it’s impossible to form k palindromes. Similarly, if k exceeds the total number of characters in the string, forming k palindromes is also not feasible.

<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
The solution begins by counting the frequency of each character in the string s. A hash map is used to store these frequencies. Next, the algorithm calculates how many characters have an odd frequency, as each odd-frequency character must be the center of its own palindrome. Finally, the function checks whether k falls between the number of odd frequencies and the total length of s. If k meets this condition, the function returns true, indicating it is possible to form k palindromes. Otherwise, it returns false.
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
- Counting character frequencies: 
O(n), where 
n is the length of 𝑠.
Counting odd frequencies: 
O(26)=O(1), since there are at most 26 lowercase English letters.
Overall: O(n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
- Hash map to store frequencies: 
O(26)=O(1) because the character set is limited to lowercase English letters.
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
#include <unordered_map>
#include <string>
using namespace std;

class Solution {
public:
    bool canConstruct(string s, int k) {
        // If k is greater than the length of s, it's impossible to create k palindromes
        if (k > s.size()) return false;
        
        // Count the frequency of each character
        unordered_map<char, int> freq;
        for (char c : s) {
            freq[c]++;
        }
        
        // Count characters with odd frequencies
        int oddCount = 0;
        for (auto [char_, count] : freq) {
            if (count % 2 != 0) {
                oddCount++;
            }
        }
        
        // If k is less than the number of odd frequencies, we can't construct k palindromes
        return k >= oddCount;
    }
};

```
['Hash Table', 'String', 'Greedy', 'Counting', 'C++']