✅🔥BEATS 100%🔥|| 🌟✅ Efficient Palindrome Building: A Beginner-Friendly Solution! 🧩💡|| Approved ✅
IntuitionThe problem is to check whether we can rearrange the characters of the string s to form exactly k palindrome strings.
Key observations:
A palindrome ca
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem is to check whether we can rearrange the characters of the string `s` to form exactly `k` palindrome strings.  
Key observations:
- A **palindrome** can have at most one character with an odd frequency.
- To form `k` palindromes, the string must have at most `k` characters with odd frequencies.
- If the length of `s` is less than `k`, it’s impossible to form `k` palindromes since there aren't enough characters.

![Screenshot 2025-01-11 091412.png](https://assets.leetcode.com/users/images/6ac8649f-2ff5-427f-8856-e5ae016180bb_1736567076.0732205.png)


# Approach
<!-- Describe your approach to solving the problem. -->
1. **Initial Check:**
   - If the size of the string `s` is less than `k`, return `false` because it's impossible to form more palindromes than the number of characters available.

2. **Frequency Count:**
   - Use a frequency array of size 26 to count the occurrences of each character in `s` (since there are 26 lowercase English letters).

3. **Count Odd Frequencies:**
   - Traverse the frequency array to count how many characters have an odd frequency. Each odd frequency requires its own palindrome.

4. **Decision:**
   - If the number of odd frequencies (`odds`) is greater than `k`, return `false` because there aren't enough palindromes to accommodate the odd frequencies.
   - Otherwise, return `true`, as it's feasible to form exactly `k` palindromes.


# Complexity
- **Time Complexity:**  
  - Calculating the frequency array takes \(O(n)\), where \(n\) is the size of the string.
  - Traversing the frequency array (size 26) takes \(O(26)\), which is constant.  
  **Total:** O(n)

- **Space Complexity:**  
  - The frequency array requires \(O(26)\), which is constant and considered \(O(1)\).  
  **Total:** O(1)

# Code
``` c []
bool canConstruct(char* s, int k) {
    int length = strlen(s);
    if (length < k)
        return false;

    int freq[26] = {0};
    
    for (int i = 0; s[i] != '\0'; i++) {
        freq[s[i] - 'a']++;
    }

    int odds = 0;
    for (int i = 0; i < 26; i++) {
        if (freq[i] % 2 != 0)
            odds++;
    }

    return odds <= k;
}
```
```cpp []
class Solution {
public:
    bool canConstruct(string s, int k) {
        if (s.size() < k)
            return false;
        vector<int> freq(26, 0);
        for (const char& c : s) {
            freq[c - 'a']++;
        }
        int odds = 0;
        for (int i = 0; i < 26; i++) {
            if (freq[i] % 2 != 0)
                odds++;
        }
        return odds <= k;
    }
};
```
```python3 []
class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if len(s) < k:
            return False
        
        from collections import Counter
        freq = Counter(s)
        
        odds = sum(1 for count in freq.values() if count % 2 != 0)
        
        return odds <= k
```
``` java []
class Solution {
    public boolean canConstruct(String s, int k) {
        if (s.length() < k)
            return false;
        
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }
        
        int odds = 0;
        for (int count : freq) {
            if (count % 2 != 0)
                odds++;
        }
        
        return odds <= k;
    }
}
```
``` javascript []
var canConstruct = function(s, k) {
    if (s.length < k) 
        return false;
    
    const freq = new Array(26).fill(0);
    for (const char of s) {
        freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    let odds = 0;
    for (const count of freq) {
        if (count % 2 !== 0)
            odds++;
    }
    
    return odds <= k;
};
```

### Example 1:

**Input:**  
`s = "annabelle", k = 2`  

**Steps:**  
1. **Initial Check:**  
   - The length of `s` is 9, which is greater than `k` (2), so we proceed.  

2. **Frequency Count:**  
   - `{'a': 2, 'n': 2, 'b': 1, 'e': 3, 'l': 2}`  

3. **Count Odd Frequencies:**  
   - Characters `b` and `e` have odd frequencies (`odds = 2`).  

4. **Decision:**  
   - Since `odds (2) <= k (2)`, it is possible to form 2 palindromes.  

**Output:**  
`true`  

**Explanation:**  
You can construct two palindromes using all characters in `s`.  
Some possible constructions:  
- `"anna" + "elble"`  
- `"anbna" + "elle"`  
- `"anellena" + "b"`  

---

### Example 2:

**Input:**  
`s = "leetcode", k = 3`  

**Steps:**  
1. **Initial Check:**  
   - The length of `s` is 8, which is greater than `k` (3), so we proceed.  

2. **Frequency Count:**  
   - `{'l': 1, 'e': 3, 't': 1, 'c': 1, 'o': 1, 'd': 1}`  

3. **Count Odd Frequencies:**  
   - Characters `l`, `t`, `c`, `o`, and `d` have odd frequencies (`odds = 5`).  

4. **Decision:**  
   - Since `odds (5) > k (3)`, it is not possible to form 3 palindromes.  

**Output:**  
`false`  

**Explanation:**  
It is impossible to construct 3 palindromes using all the characters of `s`.

---

### Example 3:

**Input:**  
`s = "true", k = 4`  

**Steps:**  
1. **Initial Check:**  
   - The length of `s` is 4, which is equal to `k` (4), so we proceed.  

2. **Frequency Count:**  
   - `{'t': 1, 'r': 1, 'u': 1, 'e': 1}`  

3. **Count Odd Frequencies:**  
   - All characters have odd frequencies (`odds = 4`).  

4. **Decision:**  
   - Since `odds (4) = k (4)`, it is possible to form 4 palindromes.  

**Output:**  
`true`  

**Explanation:**  
The only possible solution is to put each character in a separate string.  
Result: `"t"`, `"r"`, `"u"`, `"e"`.  


# Key Points  
- **Odd Frequency Check:** Counts characters with odd frequencies to determine palindrome feasibility.  
- **Efficient Filtering:** Skips unnecessary checks by comparing string length with `k` upfront, ensuring early exits for invalid cases.  
- **Handles Edge Cases:** Works seamlessly for strings shorter than `k` or with all odd frequencies.  
- **Optimal for Large Inputs:** Uses a single pass for frequency calculation and a fixed-size array, ensuring efficiency even for long strings.  
- **Clean & Readable Code:** Well-structured logic with comments, making it easy to understand and maintain.  

🌟 **Why You'll Love This Solution!**  
- **Clear & Simple 💡:** Designed for maximum readability.  
- **100% Efficiency Approved 🏆:** Handles both edge cases and large datasets effectively.  
- **Reusable 🎨:** Can be used for any string and `k` combinations.  

💖 **Show Your Support!** 👍  
If this explanation helped you understand the problem and solution, hit that like button and share your feedback below. Your encouragement fuels more optimized solutions! 🚀✨  

# UpVote 🏆
![images.jpeg](https://assets.leetcode.com/users/images/883bb385-a50e-4cdc-a4ec-e95eac5820ef_1736568208.782691.jpeg)



['C', 'C++', 'Java', 'Python3', 'JavaScript']