# Construct K Palindrome Strings LeetCode Solution

Difficulty Level Medium

## Problem Statement

Construct K Palindrome Strings LeetCode Solution – Given a string `s` and an integer `k`, return `true` if you can use all the characters in `s` to construct `k` palindrome strings or `false` otherwise.

```Input: s = "annabelle", k = 2
Output: true
Explanation: You can construct two```

palindromes using all characters

``` in s.
Some possible constructions "anna" + "elble", "anbna" + "elle", "anellena" + "b"```

## Explanation

The trick is to understand that the characters which occur an odd number of times will form a separate palindromic string each time consisting of either a single character or being present in the mid of a string. So, if the count of odd characters happens to be more than k, we return a false and likewise follow.

Also if the number of characters in s is less than k then it’s in no way possible to make k palindromic strings out of it.

For all other cases, we can make k palindromic strings.

Count the character having an odd frequency(countodd)
if(countodd<=k) return true;
else
return false

## Code

### C++ Code For Construct K Palindrome Strings

```class Solution {
public:
bool canConstruct(string s, int k) {
unordered_map<char,int> freq;
for(char ch:s)
{
freq[ch]++;
}
int oddCount=0;
for(auto pr:freq)
{
if(pr.second%2)
{
oddCount++;
}
}
return oddCount<=k&&k<=s.length();
}
};```

### Java Code For Construct K Palindrome Strings

```class Solution {
public boolean canConstruct(String s, int k) {
int n = s.length();
if (n==k) return true;
else if (n<k) return false;
int [] cnt = new int[26];
for (int i = 0; i<n; i++) cnt[s.charAt(i)-'a']++;
int odd_chars = 0;
for (int i = 0; i<26; i++) {
if (cnt[i]==0) continue;
if (cnt[i]%2!=0) odd_chars++;
}
if (odd_chars>k) return false;
else return true;
}
}```

### Python Code For Construct K Palindrome Strings

```class Solution:
def canConstruct(self, s: str, k: int) -> bool:
count = collections.Counter(s)
odd = 0
for i in count:
if count[i] % 2:
odd += 1
if odd > k:return False
return len(s) >=  k
```

## Complexity Analysis for Construct K Palindrome Strings LeetCode Solution

### Time Complexity

O(N) as we need to visit each character to calculate its count.

### Space Complexity

O(N) we store the frequencies of characters in a hash-map or frequency array so it would take O(n) space.

Reference: https://en.wikipedia.org/wiki/Palindrome

Translate »