🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏| With illustrative diagram
Problem: Construct k Palindrome StringsGiven a string s and an integer k, determine if it is possible to construct exactly k palindrome strings using all the ch
![image.png](https://assets.leetcode.com/users/images/77e9d4ae-42dd-4862-aca8-5f07c1411980_1736595465.0244067.png)


---
![1000060782.png](https://assets.leetcode.com/users/images/627a80cc-2efa-4302-804f-f3ac966d5c79_1736595768.5801446.png)

---

### Problem: Construct k Palindrome Strings

Given a string `s` and an integer `k`, determine if it is possible to construct exactly `k` palindrome strings using all the characters of `s`. 

---

### **Intuition**

1. **Palindrome Basics**:  
   - A palindrome requires characters to appear in pairs, except for at most one character that can appear an odd number of times (for the middle of the palindrome).
2. **Core Idea**:  
   - If the number of characters with odd frequencies in `s` is greater than `k`, it's impossible to construct `k` palindromes, as each palindrome can only tolerate one odd frequency character.  
   - Additionally, if the total length of the string is less than `k`, it's impossible to construct `k` palindromes because each palindrome must have at least one character.

---

### **Approach**

1. **Initial Checks**:  
   - If the length of `s` is less than `k`, return `false` (not enough characters for `k` palindromes).  
   - If the length of `s` equals `k`, return `true` (each character can be its own palindrome).
   
2. **Count Character Frequencies**:  
   - Use a map to count the frequency of each character in `s`.

3. **Count Odd Frequencies**:  
   - Iterate over the frequency map to count characters with odd frequencies.

4. **Final Check**:  
   - If the number of odd-frequency characters is less than or equal to `k`, return `true` (it's possible to group them into palindromes).  
   - Otherwise, return `false`.

---

### **Complexity**


![image.png](https://assets.leetcode.com/users/images/9ee87dd6-0460-4731-b89a-e4cab1f37f1a_1736595486.5717392.png)


  - Counting character frequencies: $$O(n)$$  
  - Iterating through the frequency map: $$O(26)$$ (constant for a fixed alphabet size, e.g., lowercase English letters).  
  **Overall**: $$O(n)$$.  

- **Space Complexity**:  
  - Frequency map requires $$O(26)$$ space for a fixed alphabet.  
  **Overall**: $$O(1)$$ for constant space (fixed alphabet).

---


```dart []
class Solution {
  bool canConstruct(String s, int k) {
    // If length of string is less than k, it's not possible
    if (s.length < k) return false;
    // If length equals k, every character can form its own palindrome
    if (s.length == k) return true;

    // Count character frequencies
    Map<String, int> freqMap = {};
    for (String char in s.split('')) {
      freqMap[char] = (freqMap[char] ?? 0) + 1;
    }

    // Count characters with odd frequencies
    int oddCount = 0;
    for (var freq in freqMap.values) {
      if (freq.isOdd) oddCount++;
    }

    // If odd frequencies are less than or equal to k, return true
    return oddCount <= k;
  }
}
```


```python []
class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        # If length of string is less than k, it's not possible
        if len(s) < k:
            return False
        # If length equals k, each character can form its own palindrome
        if len(s) == k:
            return True

        # Count character frequencies
        from collections import Counter
        freq = Counter(s)

        # Count characters with odd frequencies
        odd_count = sum(1 for count in freq.values() if count % 2 != 0)

        # If odd frequencies are less than or equal to k, return true
        return odd_count <= k
```


```java []
import java.util.*;

class Solution {
    public boolean canConstruct(String s, int k) {
        // If length of string is less than k, it's not possible
        if (s.length() < k) return false;
        // If length equals k, each character can form its own palindrome
        if (s.length() == k) return true;

        // Count character frequencies
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }

        // Count characters with odd frequencies
        int oddCount = 0;
        for (int freq : freqMap.values()) {
            if (freq % 2 != 0) oddCount++;
        }

        // If odd frequencies are less than or equal to k, return true
        return oddCount <= k;
    }
}
```


```cpp []
#include <unordered_map>
#include <string>
using namespace std;

class Solution {
public:
    bool canConstruct(string s, int k) {
        // If length of string is less than k, it's not possible
        if (s.length() < k) return false;
        // If length equals k, each character can form its own palindrome
        if (s.length() == k) return true;

        // Count character frequencies
        unordered_map<char, int> freqMap;
        for (char c : s) {
            freqMap[c]++;
        }

        // Count characters with odd frequencies
        int oddCount = 0;
        for (auto& [char, freq] : freqMap) {
            if (freq % 2 != 0) oddCount++;
        }

        // If odd frequencies are less than or equal to k, return true
        return oddCount <= k;
    }
};
```


```javascript []
var canConstruct = function(s, k) {
    // If length of string is less than k, it's not possible
    if (s.length < k) return false;
    // If length equals k, each character can form its own palindrome
    if (s.length === k) return true;

    // Count character frequencies
    const freqMap = {};
    for (let char of s) {
        freqMap[char] = (freqMap[char] || 0) + 1;
    }

    // Count characters with odd frequencies
    let oddCount = 0;
    for (let freq of Object.values(freqMap)) {
        if (freq % 2 !== 0) oddCount++;
    }

    // If odd frequencies are less than or equal to k, return true
    return oddCount <= k;
};
```


```go []
func canConstruct(s string, k int) bool {
    // If length of string is less than k, it's not possible
    if len(s) < k {
        return false
    }
    // If length equals k, each character can form its own palindrome
    if len(s) == k {
        return true
    }

    // Count character frequencies
    freq := make(map[rune]int)
    for _, char := range s {
        freq[char]++
    }

    // Count characters with odd frequencies
    oddCount := 0
    for _, count := range freq {
        if count%2 != 0 {
            oddCount++
        }
    }

    // If odd frequencies are less than or equal to k, return true
    return oddCount <= k
}
```

---

![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style='width:250px'}
['Hash Table', 'Greedy', 'C', 'Counting', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'Dart']