Counting | String | Solution for LeetCode#1400
IntuitionThe problem asks if it's possible to construct k palindromic strings using all characters from the given string s. The key insight is that palindromes
![image.png](https://assets.leetcode.com/users/images/529eef1b-750e-40a9-a152-c84ff563dbfc_1736555164.2082756.png)

# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem asks if it's possible to construct k palindromic strings using all characters from the given string s. The key insight is that palindromes can have at most one character with an odd count.

# Approach
<!-- Describe your approach to solving the problem. -->
1. First, check if the length of s is less than k. If so, it's impossible to create k strings.
2. Count the frequency of each character in s.
3. Count the number of characters with odd frequencies.
4. If the number of odd-frequency characters is greater than k, it's impossible to create k palindromes.
5. Otherwise, it's always possible to construct k palindromes.

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

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

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

        int[] arr=new int[26];
        for(char ch:s.toCharArray()){
            arr[ch-'a']++;
        }

        int oddCharCnt=0;
        for(int i=0; i<26; i++){
            if(arr[i]==0) continue;

            if(arr[i]%2==1){
                oddCharCnt++;
            }
        }

        if(oddCharCnt>k){
            return false;
        }

        return true;
    }
}
```
```python []
class Solution(object):
    def canConstruct(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: bool
        """
        n = len(s)
        if n < k:
            return False
        if n == k:
            return True

        arr = [0] * 26
        for ch in s:
            arr[ord(ch) - ord('a')] += 1

        oddCharCnt = sum(1 for count in arr if count % 2 == 1)

        return oddCharCnt <= k
        
```
['Python', 'Java', 'Python3']