A Dance of Odd Frequencies | One Pass Solution | Beats 100%
IntuitionTo determine if it's possible to construct exactly k palindrome strings using all the characters in s, I focused on the properties of palindromes. A pa
# Intuition
To determine if it's possible to construct exactly `k` palindrome strings using all the characters in `s`, I focused on the properties of palindromes. A palindrome can have at most one odd-frequency character. Thus, the number of odd-frequency characters in `s` dictates the minimum number of palindromes required.

# Approach
1. **Check if `k` exceeds the length of `s`**: If `k > s.size()`, it's impossible to construct `k` palindromes, as there aren't enough characters.
2. **Count odd-frequency characters**:
   - Use a frequency array to track the character counts.
   - For each character, toggle between odd and even frequency.
3. **Compare odd frequencies with `k`**:
   - If `odd <= k`, we can form the required palindromes.
   - Otherwise, it's not possible.

# Complexity
- Time complexity:  
  $$O(n)$$, where \(n\) is the length of `s`, as we traverse the string and process character frequencies.

- Space complexity:  
  $$O(1)$$, since the frequency array has a fixed size of 26 (for lowercase letters).

# Code
```cpp
class Solution {
public:
    bool canConstruct(string s, int k) {
        if(k > s.size()) return 0;

        vector<int> v(26, 0);
        int odd = 0;

        for(auto d: s) {
            v[d - 'a']++;

            if(v[d - 'a'] % 2) odd++;
            else odd--;
        }

        if(k >= odd) return 1;
        return 0;
    }
};
```
#### If you have any questions or concerns about my solution, feel free to leave a comment instead of downvoting—I'd love to help! 😊 And if you found my solution helpful, please consider giving it an upvote. Your support means a lot and lets me know I made a difference! 🙌
['Hash Table', 'String', 'Greedy', 'Counting', 'C++']