C++ Solution + YouTube Tutorial 🎬💖
IntuitionTo determine if a string can be split into exactly k palindromes, the key insight is understanding the properties of palindromes:
A palindrome can have
# Intuition
To determine if a string can be split into exactly `k` palindromes, the key insight is understanding the properties of palindromes:
1. A palindrome can have at most **one character** with an odd frequency.
2. The number of characters with odd frequencies determines the **minimum number of palindromes** needed.

Using these observations, we can infer that:
- If the number of odd-frequency characters (`single`) exceeds `k`, it’s impossible to create `k` palindromes.
- If `k` is greater than the length of the string, it’s also impossible because there aren't enough characters.

Thus, we need to:
1. Count the frequency of each character.
2. Count how many characters have an odd frequency.
3. Check if `k` lies within the valid range: `single <= k <= s.size()`.

---

# Approach
1. Use a hash map to count the frequency of each character in the string.
2. Count the number of characters with odd frequencies (`single`).
3. Validate the range:
   - If `k` is greater than or equal to `single` (minimum required palindromes) and less than or equal to the string length (`s.size()`), return `true`.
   - Otherwise, return `false`.

---

# Complexity
- **Time complexity**:  
  $$O(n)$$  
  - Iterating through the string to count frequencies takes \(O(n)\).  
  - Iterating through the hash map (maximum 26 entries for lowercase English letters) takes \(O(1)\).

- **Space complexity**:  
  $$O(1)$$  
  - The hash map stores at most 26 keys (fixed size for lowercase English letters).


---

# YouTube Tutorial
🎥 **Watch the full explanation on YouTube**: 
<iframe width="560" height="315" src="https://www.youtube.com/embed/sqKDUZ3yLpY" title="YouTube video tutorial for Word Subsets - LeetCode 916" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>


In this tutorial, we:
- Explain the intuition behind the solution.
- Walk through examples step-by-step.
- Write and analyze the C++ code.

---
# Code
```cpp
class Solution {
public:
    bool canConstruct(string s, int k) {
        unordered_map<char, int> freq;
        int single = 0;

        // Count character frequencies
        for (auto c : s) {
            freq[c]++;
        }

        // Count odd frequencies
        for (auto &[c, count] : freq) {
            if (count % 2 == 1) {
                single++;
            }
        }

        // Check if k is in the valid range
        return k >= single && k <= s.size();
    }
};
```

Don’t forget to **like**, **subscribe**, and **comment** with your thoughts or questions!

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