Most Optimized Solution | ✅Beats 100% | C++| Java | Python | JavaScript
IntuitionTo construct k palindromes, we need to understand that each palindrome can have at most one character with odd frequency (in the middle). Therefore, th
```cpp []
class Solution {
public:
    bool canConstruct(string s, int k) {
        if (k > s.length()) return false;
        int charCount[26] = {0};
        for (char c : s) {
            charCount[c - 'a']++;
        }
        int oddCount = 0;
        for (int i = 0; i < 26; i++) {
            if (charCount[i] % 2 == 1) oddCount++;
        }
        return oddCount <= k;
    }
};
```
```python []
class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if k > len(s): return False
        charCount = [0] * 26
        for c in s:
            charCount[ord(c) - ord('a')] += 1
        oddCount = 0
        for i in range(26):
            if charCount[i] % 2 == 1:
                oddCount += 1
        return oddCount <= k and k <= len(s)
```
```java []
class Solution {
    public boolean canConstruct(String s, int k) {
        if (k > s.length()) return false;
        int[] charCount = new int[26];
        for (char c : s.toCharArray()) {
            charCount[c - 'a']++;
        }
        int oddCount = 0;
        for (int i = 0; i < 26; i++) {
            if (charCount[i] % 2 == 1) oddCount++;
        }
        return oddCount <= k && k <= s.length();
    }
}
```
```javascript []
class Solution {
    canConstruct(s, k) {
        if (k > s.length) return false;
        const charCount = new Array(26).fill(0);
        for (let c of s) {
            charCount[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }
        let oddCount = 0;
        for (let i = 0; i < 26; i++) {
            if (charCount[i] % 2 === 1) oddCount++;
        }
        return oddCount <= k && k <= s.length;
    }
}
```

# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
To construct k palindromes, we need to understand that each palindrome can have at most one character with odd frequency (in the middle). Therefore, the total number of characters with odd frequencies must not exceed k.

# Approach
<!-- Describe your approach to solving the problem. -->
1. First check if k is larger than string length - if yes, return false
2. Count frequency of each character using an array of size 26
3. Count total number of characters with odd frequencies
4. Return true if odd count ≤ k and k ≤ string length

# Complexity
- Time complexity: $$O(n)$$ where n is the length of string s
- Space complexity: $$O(1)$$ as we use fixed size array of 26 characters

### *If you have any questions or need further clarification, feel free to drop a comment! 😊*
['String', 'Greedy', 'Counting', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']