✅🔥BEATS 99%🔥 || 3 UNIQUE APPROACHES TO Construct K Palindrome Strings 💡|| CONCISE CODE ✅
💡IntuitionThe problem revolves around the frequency of characters in a string. To construct palindromes:
Characters with odd frequencies must be the centers of
![image.png](https://assets.leetcode.com/users/images/9e0c10d2-2543-41a4-97cc-67526440bfce_1736604917.92514.png)


# 💡Intuition  
The problem revolves around the frequency of characters in a string. To construct palindromes:  
1. Characters with **odd frequencies** must be the centers of palindromes.  
2. The number of odd frequencies determines the **minimum number of palindromes** required.  
3. If the total odd frequencies ≤ `k`, the task is feasible.  

---

# 🔍Approach 1: Sorting and Grouping  

## Explanation  
- **Sort the String**: Group identical characters together.  
- **Count Odd Frequencies**: Traverse the sorted characters, counting the ones with odd frequencies.  
- **Check Feasibility**: Ensure the number of odd frequencies is ≤ `k`.  

---

# 💻Complexity  
- **Time Complexity**:  
  $$O(n \log n)$$ — Sorting the string.  

- **Space Complexity**:  
  $$O(n)$$ — For storing the sorted characters.  

---

# Code  
```python []
class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if len(s) < k:
            return False
        sorted_s = sorted(s)
        
        odd_count = 0
        i = 0
        
        while i < len(sorted_s):
            char = sorted_s[i]
            count = 0
            while i < len(sorted_s) and sorted_s[i] == char:
                count += 1
                i += 1
            if count % 2 == 1:
                odd_count += 1
        
        return odd_count <= k
```
``` cpp []
class Solution {
public:
    bool canConstruct(string s, int k) {
        if (s.length() < k) return false;

        sort(s.begin(), s.end());
        int oddCount = 0;

        for (int i = 0; i < s.length(); ) {
            char current = s[i];
            int count = 0;
            while (i < s.length() && s[i] == current) {
                count++;
                i++;
            }
            if (count % 2 != 0) oddCount++;
        }

        return oddCount <= k;
    }
};
```
``` java []
import java.util.Arrays;

class Solution {
    public boolean canConstruct(String s, int k) {
        if (s.length() < k) return false;

        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        int oddCount = 0;

        for (int i = 0; i < chars.length; ) {
            char current = chars[i];
            int count = 0;
            while (i < chars.length && chars[i] == current) {
                count++;
                i++;
            }
            if (count % 2 != 0) oddCount++;
        }

        return oddCount <= k;
    }
}
```
``` javascript []
var canConstruct = function(s, k) {
    if (s.length < k) return false;

    let chars = [...s].sort();
    let oddCount = 0;

    for (let i = 0; i < chars.length; ) {
        let current = chars[i];
        let count = 0;
        while (i < chars.length && chars[i] === current) {
            count++;
            i++;
        }
        if (count % 2 !== 0) oddCount++;
    }

    return oddCount <= k;
};
```
``` ruby []
def can_construct(s, k)
    return false if s.length < k

    chars = s.chars.sort
    odd_count = 0

    i = 0
    while i < chars.length
        current = chars[i]
        count = 0
        while i < chars.length && chars[i] == current
            count += 1
            i += 1
        end
        odd_count += 1 if count.odd?
    end

    odd_count <= k
end
```
``` go []
func canConstruct(s string, k int) bool {
    if len(s) < k {
        return false
    }

    chars := []rune(s)
    sort.Slice(chars, func(i, j int) bool { return chars[i] < chars[j] })
    oddCount := 0

    for i := 0; i < len(chars); {
        current := chars[i]
        count := 0
        for i < len(chars) && chars[i] == current {
            count++
            i++
        }
        if count%2 != 0 {
            oddCount++
        }
    }

    return oddCount <= k
}
```
``` csharp []
using System;

public class Solution {
    public bool CanConstruct(string s, int k) {
        if (s.Length < k) return false;

        char[] chars = s.ToCharArray();
        Array.Sort(chars);
        int oddCount = 0;

        for (int i = 0; i < chars.Length; ) {
            char current = chars[i];
            int count = 0;
            while (i < chars.Length && chars[i] == current) {
                count++;
                i++;
            }
            if (count % 2 != 0) oddCount++;
        }

        return oddCount <= k;
    }
}
```
# 🔍Approach 2: Bitmasking

## Explanation
- Each character corresponds to a specific bit in a bitmask (e.g., `'a'` is the 0th bit, `'b'` is the 1st bit, etc.).
- Toggle the bits for each character in the string:
  - If a bit is `1`, it indicates an odd frequency.
  - If a bit is `0`, it indicates an even frequency.
- Count the number of `1`s in the bitmask to determine how many characters have odd frequencies.
- If the number of odd frequencies is ≤ `k`, constructing `k` palindromes is possible.

---

## 💻Complexity
- **Time Complexity**:  
  $$O(n)$$ — Iterate through the string and count set bits.  
- **Space Complexity**:  
  $$O(1)$$ — Constant space used for the bitmask.

---

# Code
```python []
class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if len(s) < k:
            return False

        bitmask = 0
        for char in s:
            bitmask ^= (1 << (ord(char) - ord('a')))

        odd_count = bin(bitmask).count('1')
        return odd_count <= k
```
``` cpp []
class Solution {
public:
    bool canConstruct(string s, int k) {
        if (s.length() < k) return false;

        int bitmask = 0;
        for (char c : s) {
            bitmask ^= (1 << (c - 'a'));
        }

        int oddCount = __builtin_popcount(bitmask);
        return oddCount <= k;
    }
};
```
``` java []
class Solution {
    public boolean canConstruct(String s, int k) {
        if (s.length() < k) return false;

        int bitmask = 0;
        for (char c : s.toCharArray()) {
            bitmask ^= (1 << (c - 'a'));
        }

        int oddCount = Integer.bitCount(bitmask);
        return oddCount <= k;
    }
}
``` 
``` javascript []
var canConstruct = function(s, k) {
    if (s.length < k) return false;

    let bitmask = 0;
    for (let char of s) {
        bitmask ^= (1 << (char.charCodeAt(0) - 'a'.charCodeAt(0)));
    }

    let oddCount = bitmask.toString(2).split('1').length - 1;
    return oddCount <= k;
};
```
``` ruby []
def can_construct(s, k)
    return false if s.length < k

    bitmask = 0
    s.each_char do |char|
        bitmask ^= (1 << (char.ord - 'a'.ord))
    end

    odd_count = bitmask.to_s(2).count('1')
    odd_count <= k
end
```
``` go []
func canConstruct(s string, k int) bool {
    if len(s) < k {
        return false
    }

    bitmask := 0
    for _, char := range s {
        bitmask ^= (1 << (char - 'a'))
    }

    oddCount := 0
    for bitmask > 0 {
        oddCount += bitmask & 1
        bitmask >>= 1
    }

    return oddCount <= k
}
```
``` csharp []
using System;

public class Solution {
    public bool CanConstruct(string s, int k) {
        if (s.Length < k) return false;

        int bitmask = 0;
        foreach (char c in s) {
            bitmask ^= (1 << (c - 'a'));
        }

        int oddCount = CountSetBits(bitmask);
        return oddCount <= k;
    }

    private int CountSetBits(int n) {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
}
```
# 🔍Approach 3: Using a Counter

## Explanation
- Count the frequency of each character in the string using a `Counter`.
- Determine how many characters have an odd frequency.
- If the number of odd frequencies is greater than `k`, constructing `k` palindromes is not possible.
- Otherwise, it is possible.

---

## 💻Complexity
- **Time Complexity**:  
  $$O(n)$$ — Counting characters and calculating the number of odd frequencies.  
- **Space Complexity**:  
  $$O(1)$$ — Fixed space for the character count (max 26 letters for English alphabet).

---

# Code  
```python []
from collections import Counter

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if len(s) < k:
            return False

        char_count = Counter(s)
        odd_count = sum(freq % 2 for freq in char_count.values())
        return odd_count <= k
```
``` cpp []
#include <unordered_map>
using namespace std;

class Solution {
public:
    bool canConstruct(string s, int k) {
        if (s.length() < k) return false;

        unordered_map<char, int> charCount;
        for (char c : s) {
            charCount[c]++;
        }

        int oddCount = 0;
        for (auto& entry : charCount) {
            if (entry.second % 2 != 0) oddCount++;
        }

        return oddCount <= k;
    }
};
``` 
``` java []
import java.util.HashMap;

class Solution {
    public boolean canConstruct(String s, int k) {
        if (s.length() < k) return false;

        HashMap<Character, Integer> charCount = new HashMap<>();
        for (char c : s.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }

        int oddCount = 0;
        for (int freq : charCount.values()) {
            if (freq % 2 != 0) oddCount++;
        }

        return oddCount <= k;
    }
}

```
``` javascript []
var canConstruct = function(s, k) {
    if (s.length < k) return false;

    let charCount = {};
    for (let char of s) {
        charCount[char] = (charCount[char] || 0) + 1;
    }

    let oddCount = 0;
    for (let count of Object.values(charCount)) {
        if (count % 2 !== 0) oddCount++;
    }

    return oddCount <= k;
};
```
``` ruby []
def can_construct(s, k)
    return false if s.length < k

    char_count = Hash.new(0)
    s.each_char { |char| char_count[char] += 1 }

    odd_count = char_count.values.count { |count| count.odd? }
    odd_count <= k
end
```
``` go []
func canConstruct(s string, k int) bool {
    if len(s) < k {
        return false
    }

    charCount := make(map[rune]int)
    for _, char := range s {
        charCount[char]++
    }

    oddCount := 0
    for _, count := range charCount {
        if count%2 != 0 {
            oddCount++
        }
    }

    return oddCount <= k
}
```
``` csharp []
using System;
using System.Collections.Generic;

public class Solution {
    public bool CanConstruct(string s, int k) {
        if (s.Length < k) return false;

        Dictionary<char, int> charCount = new Dictionary<char, int>();
        foreach (char c in s) {
            if (!charCount.ContainsKey(c)) {
                charCount[c] = 0;
            }
            charCount[c]++;
        }

        int oddCount = 0;
        foreach (int count in charCount.Values) {
            if (count % 2 != 0) oddCount++;
        }

        return oddCount <= k;
    }
}
``` 
# ✅Conclusion

---

We explored three distinct approaches to solving the "Construct K Palindrome Strings" problem. Each approach has its unique strengths and trade-offs:

1. **Approach 1: Sorting the String**
   - Simple and intuitive, but has a time complexity of \(O(n \log n)\), making it less efficient for larger inputs.
   
2. **Approach 2: Bitmasking**
   - Efficient in terms of space (\(O(1)\)) and time (\(O(n)\)) as we utilize bit manipulation to track character frequencies. Best for problems where we're working with small alphabets (like lowercase English letters).

3. **Approach 3: Using a Counter**
   - Very clear and easy to implement using a counter to track character frequencies. Time complexity is linear \(O(n)\) and space complexity is constant \(O(1)\) for the alphabet size.

In practice, **Approach 3 (Using a Counter)** is often the most straightforward and efficient for typical use cases, especially when combined with the simplicity of built-in data structures. However, **Approach 2 (Bitmasking)** shines when optimization is a top priority, particularly with respect to space usage.

Each approach is valid and the best one depends on the problem's constraints and the developer's familiarity with the concepts.

![WhatsApp Image 2025-01-09 at 07.24.23_943689d3.jpg](https://assets.leetcode.com/users/images/b1d14dba-581c-4546-b91b-6c75da98a4fd_1736562701.948354.jpeg)

['C++', 'Java', 'Go', 'Python3', 'Ruby', 'C#']