0ms | Beats 100%| Using Bitmask Based (13Line) | Efficient & Easy C++ Solu| Full Explain| With Proof
IntuitionThe problem revolves around determining whether a given string can be split into k palindromic substrings. A palindrome is a string that reads the same
![11 jan.jpg](https://assets.leetcode.com/users/images/b59bfc2b-a279-4fae-8530-ab585ec81ea6_1736557655.6304543.jpeg)


# Intuition
The problem revolves around determining whether a given string can be split into k palindromic substrings. A palindrome is a string that reads the same forward and backward. The key to solving this problem lies in understanding the frequency of characters in the string:

1. Palindrome Character Properties:

- In a palindrome, characters must pair up to form the string symmetrically. This means most characters should appear an even number of times.
- The only exception is that one character can appear an odd number of times and sit in the middle of the palindrome if the length of the palindrome is odd.
2. Odd Frequencies and Palindromes:

- To form palindromes from the string, the number of characters that appear an odd number of times is crucial.
- Specifically, we can have at most k characters with odd frequencies, because in the worst case, each odd frequency can form the middle of a distinct palindrome. If we have more than k characters with odd frequencies, it becomes impossible to split the string into k palindromes.
3. Tracking Odd Frequencies Efficiently:

- We need to count how many characters in the string have an odd frequency. Instead of explicitly counting frequencies, we can use a bitmask to efficiently track this information.
- Each bit in the bitmask corresponds to a character ('a' to 'z'). The bit is set to 1 if the character has an odd frequency and 0 if it has an even frequency.
- After processing the string, the number of set bits (1s) in the bitmask represents how many characters have an odd frequency.
4. Final Check:

- If the number of characters with odd frequencies (i.e., the number of set bits in the bitmask) is less than or equal to k, then it is possible to split the string into k or more palindromic substrings. Otherwise, it’s not possible.
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
1. Edge Case Handling:

- If the length of the string `s` is less than` k`, return false. You can’t have more palindromes than the number of characters.
- If the length of` s` equals `k`, return true. Each character can be its own palindrome.
2. Track Odd Frequencies Using Bitmasking:

- Initialize an integer `oddCount` to represent a bitmask. Each bit corresponds to a character ('a' to 'z'), and toggling the bits will track whether a character’s frequency is odd or even.
- For each character in the string, use XOR operation to toggle the corresponding bit in` oddCount`:
-- If a character’s frequency is odd, its corresponding bit will be set to 1.
-- If a character’s frequency is even, its corresponding bit will be set to 0.
3. Count Set Bits (Odd Frequencies):

- The number of set bits in the` oddCount` bitmask directly represents the number of characters that have odd frequencies.
- Use `__builtin_popcount() `to efficiently count the number of set bits in oddCount.
4. Final Check:

- If the number of odd frequencies (set bits in the bitmask) is less than or equal to` k`, return true. It is possible to split the string into k or more palindromic substrings.
- Otherwise, return false.
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity: **𝑂(𝑛)** , where 𝑛 is the length of the string.
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: **𝑂(1)** , where it is Constant because does not depend on the size of the input string
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    bool canConstruct(string s, int k) {
        if (s.length() < k) return false;
        if (s.length() == k) return true;
        int oddCount = 0;
        for (char chr : s) {
            oddCount ^= 1 << (chr - 'a');
        }
        int setBits = __builtin_popcount(oddCount);
        return setBits <= k;
    }
};
```

![5e54ce8f-85c3-42eb-b14a-80d9b90e23c0_1736389445.0482821.jpeg](https://assets.leetcode.com/users/images/0c14e71f-e23b-427b-8a5e-39ce99e35bd5_1736557673.6314418.jpeg)

['Hash Table', 'String', 'Greedy', 'Bit Manipulation', 'Counting', 'Ordered Set', 'Counting Sort', 'Bitmask', 'C++']