Only Count Odd Frequencies - Explanation | C++, Python, Java
ApproachWe can use a greedy approach to find our solution. In our greedy approach, we'll mostly only focus on palindromes consisting of one specific character u
# Approach
<!-- Describe your approach to solving the problem. -->
We can use a greedy approach to find our solution. In our greedy approach, we'll mostly only focus on palindromes consisting of one specific character until the end. First we'll get the frequency of each character in `s` with a frequency array `freq[26]`.

Firstly, if `s.length()` we can return False immediately since it would be impossible to form $$k$$ palindromes with less than $$k$$ characters.

For this problem, we only need to check the number of characters with odd frequencies is less than `k`. In a valid palindrome, only one character can have an odd frequency with every other having an even frequency to help mirror the string around the center. Therefore, when we have characters with odd frequencies in our greedy approach, they must stand alone. This makes the minimum number of palindromes we can form with all the characters in `s` equal to the number of characters with odd frequencies.

But what about characters with even frequencies. These actually don't create any additional constraints on the problem as in the end they can be distributed in any way needed. For example, if we have 5 characters with odd frequencies (meaning 5 palindromes already), `k = 6`, and 20 other unique characters each with even frequencies, we can simply create 1 palindrome with the rest of the characters since they all have even frequencies.

The same is true for the odd frequency characters. If there's less tha k of them then we can create the other needed palindromes either with single characters or combining them with the other even-frequency characters.

# Complexity
- Time complexity: $$O(n)$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(1)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```C++ []
class Solution {
public:
    bool canConstruct(string s, int k) {
        if (s.length() < k)
            return false;
        int freq[26] = {};
        for (char c : s)
            freq[c - 'a']++;
        for (int i = 0; i < 26; i++)
            if ((k -= (freq[i] & 1)) < 0)
                return false;
        return true;
    }
};
```
```python []
class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        return len(s) >= k and sum(c & 1 for c in Counter(s).values()) <= k
```
```Java []
class Solution {
    public boolean canConstruct(String s, int k) {
        if (s.length() < k)
            return false;
        int[] freq = new int[26];
        for (int i = 0; i < s.length(); i++)
            freq[s.charAt(i) - 'a']++;
        for (int i = 0; i < 26; i++)
            if ((k -= freq[i] % 2) < 0)
                return false;
        return true;
    }
}
```
**Little more elegant and in one iteration:**
```cpp
bool canConstruct(string s, int k) {
    if (s.length() < k)
        return false;
    int freq[26] = {};
    for (char c : s)
        k += (++freq[c - 'a'] & 1 ? -1 : 1);
    return k >= 0;
}
```


['Hash Table', 'String', 'Greedy', 'C', 'Counting', 'Python', 'C++', 'Java', 'Python3']