✅ Simple Freq Count Detailed Solution
Can Construct Palindromes 🏗️Problem Understanding 🤔Given a string s and a number k, we need to determine if we can construct exactly k palindromes using the cha
# **Can Construct Palindromes** 🏗️

### **Problem Understanding** 🤔
Given a string `s` and a number `k`, we need to determine if we can construct exactly `k` palindromes using the characters from `s`.

---

## **Intuition** 💡
- A **palindrome** is a string that reads the same forward and backward. 
- For constructing a palindrome:
  - Characters must appear in **pairs** (even frequency).
  - At most **one** character with an **odd frequency** can be placed at the center of the palindrome.
- The challenge is to determine if it's possible to create exactly `k` palindromes from the string `s`.

---

## **Approach** 🚀
### **Step 1: Count Character Frequencies** 🧮
- Count how many times each character appears in the string `s`. 
- Use an unordered map `M` to store the frequency of each character.

### **Step 2: Count Odd Frequencies (Singles)** 🔢
- A character with an **odd frequency** will need to be placed at the center of a palindrome.
- Count how many characters have odd frequencies (`Single` count).

### **Step 3: Determine Feasibility** ✅
- If `Single <= k` and `k <= s.size()`, it's possible to create exactly `k` palindromes.
  - `Single <= k`: There must be enough "odd characters" to form the palindromes.
  - `k <= s.size()`: You cannot form more palindromes than there are characters in the string.
  - 'a': 2, 'b': 2, 'c': 2, 'd': 2, 'e': 2, 'f': 2, 'g': 1

2. **Count Singles (Odd Frequencies)**:
- `'g'` has an odd frequency (`1`), so `Single = 1`.

3. **Feasibility Check**:
- `Single = 1`
- `k = 4` (we can place the odd character `g` in one of the palindromes).
- `k = 4` is valid because it is less than or equal to the number of characters in `s` (13).

**Output:**  
Yes, it is possible to form exactly 4 palindromes. 🎉

---

## **Time and Space Complexity** ⏳

### **Time Complexity** 🕒
- Counting character frequencies takes **O(n)** where `n` is the length of the string `s`.
- Iterating over the frequencies takes **O(m)** where `m` is the number of distinct characters in `s` (which is at most `26` for lowercase English letters).
- **Overall Time Complexity: O(n)**.

### **Space Complexity** 🧑‍💻
- We are using an unordered map to store the frequency of each character.
- The space complexity is **O(m)** where `m` is the number of distinct characters in `s` (maximum `26` for lowercase letters).
- **Overall Space Complexity: O(m)**.
# [Telegram](https://t.me/leetmath)

---
![9c6f9412-c860-47d6-9a2e-7fcf37ff3321_1686334926.180891.png](https://assets.leetcode.com/users/images/9775a6a6-068d-4d4c-b146-4f92113e2a40_1736555006.41949.png)

# Code
```cpp []
class Solution {
public:
    bool canConstruct(string s, int k) {
        unordered_map<char, int> M;
        int Single = 0;

        // Count frequencies of each character
        for (char c : s) {
            M[c]++;
        }

        // Count pairs and singles
        for (auto &[ch, freq] : M) {
            if (freq % 2 == 1) {
                Single++; // Count remaining single characters
            }
        }
        return (Single <= k && k <= s.size());
    }
};

```
```Java []
class Solution {
    public boolean canConstruct(String s, int k) {
        Map<Character, Integer> M = new HashMap<>();
        int Single = 0;

        for (char c : s.toCharArray()) {
            M.put(c, M.getOrDefault(c, 0) + 1);
        }

        for (int freq : M.values()) {
            if (freq % 2 == 1) {
                Single++;
            }
        }

        return Single <= k && k <= s.length();
    }
}
```
```Python3 []
class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        freq_map = {}
        single_count = 0

        for c in s:
            freq_map[c] = freq_map.get(c, 0) + 1

        for freq in freq_map.values():
            if freq % 2 == 1:
                single_count += 1

        return single_count <= k and k <= len(s)
```
```C []
bool canConstruct(char* s, int k) {
    int freq[256] = {0};
    int single_count = 0;
    
    for (int i = 0; s[i] != '\0'; i++) {
        freq[s[i]]++;
    }

    for (int i = 0; i < 256; i++) {
        if (freq[i] % 2 == 1) {
            single_count++;
        }
    }

    return single_count <= k && k <= strlen(s);
}
```
```C# []
public class Solution {
    public bool CanConstruct(string s, int k) {
        var freqMap = new Dictionary<char, int>();
        int singleCount = 0;

        foreach (char c in s) {
            if (freqMap.ContainsKey(c)) {
                freqMap[c]++;
            } else {
                freqMap[c] = 1;
            }
        }

        foreach (var freq in freqMap.Values) {
            if (freq % 2 == 1) {
                singleCount++;
            }
        }

        return singleCount <= k && k <= s.Length;
    }
}
```
```JavaScript []
/**
 * @param {string} s
 * @param {number} k
 * @return {boolean}
 */
var canConstruct = function(s, k) {
    const freqMap = {};
    let singleCount = 0;

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

    // Count how many characters have an odd frequency
    for (const freq of Object.values(freqMap)) {
        if (freq % 2 === 1) {
            singleCount++;
        }
    }

    // Check if we can construct exactly k palindromes
    return singleCount <= k && k <= s.length;
};
```

['String', 'C', 'Counting', 'C++', 'Java', 'Python3', 'JavaScript', 'C#']