🚀 Efficient Single-Pass Solution | Fully Explained & Well-Commented 🔍| Check this out once
IntuitionIn a palindrome, all characters must appear an even number of times, except for at most one character that can appear an odd number of times (to occupy
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
In a palindrome, all characters must appear an even number of times, except for at most one character that can appear an odd number of times (to occupy the middle position). Therefore, the number of characters with odd frequencies determines the minimum number of palindromic strings that can be formed. Each character with an odd frequency must be placed in the center of a separate palindrome.

---


# Approach
<!-- Describe your approach to solving the problem. -->
1. Edge Case Check: If the length of the string s is less than k, it's impossible to split it into k non-empty palindromic strings.
2. Frequency Count: Iterate through the string and maintain a frequency array to count occurrences of each character.
3. Odd Frequency Count: Iterate through the frequency array and count how many characters have an odd frequency.
4. Validation:
    - If the number of odd-frequency characters is greater than k, forming k palindromic strings is impossible.
    - If it's less than or equal to k, it's possible, so return true.


---


![Leetcode upvote bheek.jpeg](https://assets.leetcode.com/users/images/74ef2ba6-4a11-4417-ad11-aed68960ddd3_1736556023.9622507.jpeg)

---



# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
    O(n)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
    O(1)

---


# Code
```java []
class Solution {
    public boolean canConstruct(String s, int k) {
        // If the length of the string is less than k, it's impossible to form k non-empty palindromic strings
        if (s.length() < k) {
            return false;
        }

        // Frequency array to count occurrences of each character (assuming lowercase English letters)
        int[] freq = new int[26];

        // Convert the string to a character array for easy iteration
        char[] characters = s.toCharArray();

        // Variable to count the number of characters with odd frequencies
        int unique = 0;

        // Count the frequency of each character in the string
        for (char c : characters) {
            freq[c - 'a']++;
        }

        // Count how many characters have an odd frequency
        for (int i : freq) {
            if (i % 2 != 0) {
                unique++;
            }
        }

        // The minimum number of palindromic strings needed is equal to the number of odd frequency characters
        // If unique <= k, it's possible to form k palindrome strings
        return unique <= k;
    }
}

```
```C# []
public class Solution {
    public bool CanConstruct(string s, int k) {
        // If the string length is less than k, it's impossible to form k palindromic strings
        if (s.Length < k) {
            return false;
        }

        // Frequency array for lowercase English letters
        int[] freq = new int[26];

        // Count the frequency of each character
        foreach (char c in s) {
            freq[c - 'a']++;
        }

        // Count characters with odd frequencies
        int oddCount = 0;
        foreach (int count in freq) {
            if (count % 2 != 0) {
                oddCount++;
            }
        }

        // If odd frequencies are <= k, it's possible to form k palindromic strings
        return oddCount <= k;
    }
}

```
```C++ []
class Solution {
public:
    bool canConstruct(string s, int k) {
        // If the string length is less than k, it's impossible to form k palindromic strings
        if (s.length() < k) {
            return false;
        }

        // Frequency array for lowercase English letters
        int freq[26] = {0};

        // Count the frequency of each character
        for (char c : s) {
            freq[c - 'a']++;
        }

        // Count characters with odd frequencies
        int oddCount = 0;
        for (int i = 0; i < 26; i++) {
            if (freq[i] % 2 != 0) {
                oddCount++;
            }
        }

        // If odd frequencies are <= k, it's possible to form k palindromic strings
        return oddCount <= k;
    }
};
```
```C []
bool canConstruct(char* s, int k) {
    int len = strlen(s);

    // If the string length is less than k, it's impossible to form k palindromic strings
    if (len < k) {
        return false;
    }

    // Frequency array for lowercase English letters
    int freq[26] = {0};

    // Count the frequency of each character
    for (int i = 0; i < len; i++) {
        freq[s[i] - 'a']++;
    }

    // Count characters with odd frequencies
    int oddCount = 0;
    for (int i = 0; i < 26; i++) {
        if (freq[i] % 2 != 0) {
            oddCount++;
        }
    }

    // If odd frequencies are <= k, it's possible to form k palindromic strings
    return oddCount <= k;
}

```
```javascript []
/**
 * @param {string} s
 * @param {number} k
 * @return {boolean}
 */
var canConstruct = function(s, k) {
    // If the string length is less than k, it's impossible to form k palindromic strings
    if (s.length < k) {
        return false;
    }

    // Frequency map for character counts
    const freq = new Array(26).fill(0);

    // Count the frequency of each character
    for (let char of s) {
        freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }

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

    // If odd frequencies are <= k, it's possible to form k palindromic strings
    return oddCount <= k;
};

```

---


['Hash Table', 'String', 'C', 'C++', 'Java', 'JavaScript', 'C#']