Hash | Simple Logic | Beats 100%
IntuitionOdd count characters will create problems for palindrome.All the odd frequency characters can be used as a single character string which is always a pa
![image.png](https://assets.leetcode.com/users/images/5dccd259-f85f-4ae9-9d45-c6950765ea18_1736592402.4685996.png)

# Intuition
Odd count characters will create problems for palindrome. 

**All the odd frequency characters can be used as a single character string which is always a palindrome. E.g. "a","g","l","v", etc. and one of them can be used with the remaining characters in between.**

# Approach
If string size is < k then it is not possible.
Count the frequency of each character.
Count which characters have an odd frequency and compare them with k.

E.g. s = "aabcccdd"

For k = 1 --> Not possible as b and c have odd frequencies.

For k = 2 --> b & c are the between characters and we can put remaining on both sides of them by our choice. E.g. "aca" & "dcbcd" or "adcccda" & "b" or any other combination.

For k = 3 --> "b","c" and "acddca" or "aa", "ccc" and "dbd" or any other combination.

and so on.

> So even frequency characters can be placed anywhere and only odd ones will have to be taken care of.

# Complexity
- Time complexity: O(n)

- Space complexity: O(1)

# Code
```cpp []
class Solution {
public:
    bool canConstruct(string s, int k) {
        int n = s.size();
        if (n < k) return false;

        vector<int> v(26,0);
        for (char &c: s) v[c-'a']++;
        int ct = 0;
        for (int i = 0; i < 26; i++){
            if (v[i]&1) ct++;
        }
        if (ct > k) return false;
        return true;
    }
};
```

# Upvote 👍 if you found this useful
['Hash Table', 'String', 'Counting', 'C++']