# Construct K Palindrome Strings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/construct-k-palindrome-strings)
Canonical: https://scaleengineer.com/dsa/problems/construct-k-palindrome-strings
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
---
## Problem
Given a string `s` and an integer `k`, return `true` if you can use all the characters in `s` to construct **non-empty** `k` palindrome strings or `false` otherwise.

**Example 1:**

**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"

**Example 2:**

**Input:** s = "leetcode", k = 3
**Output:** false
**Explanation:** It is impossible to construct 3 palindromes using all the characters of s.

**Example 3:**

**Input:** s = "true", k = 4
**Output:** true
**Explanation:** The only possible solution is to put each character in a separate string.

**Constraints:**

* `1 <= s.length <= 105`
* `s` consists of lowercase English letters.
* `1 <= k <= 105`

# Approaches
## Sorting-based Frequency Count
This approach first sorts the string to group identical characters together, making it easier to count their frequencies. After counting, it determines if the conditions for forming `k` palindromes are met based on the number of characters with odd frequencies.
**Time:** O(N log N), where N is the length of the string `s`. The dominant operation is sorting the character array. · **Space:** O(N), where N is the length of the string. This is because we create a character array of size N to sort. The space used by the sorting algorithm itself is typically O(log N) for quicksort but can be O(N) in the worst case.
**Pros:** Logically straightforward once the string is sorted.
**Cons:** Less efficient than using a hash map due to the `O(N log N)` sorting step.; Requires `O(N)` auxiliary space for the character array copy.
### Explanation
The core idea is that a string can be rearranged into a palindrome if at most one of its characters has an odd frequency. To construct `k` palindromes, we need to partition the characters of `s`. The main constraint comes from characters with odd frequencies in `s`. Each such character must become the center of a different palindrome.

Let `odd_count` be the number of characters with an odd frequency in `s`. We need at least `odd_count` palindromes, so `k` must be greater than or equal to `odd_count`.

Additionally, to form `k` non-empty strings, the total number of characters `s.length()` must be at least `k`.

These two conditions, `k >= odd_count` and `k <= s.length()`, are necessary and sufficient. This approach calculates `odd_count` by first sorting the string to make frequency counting straightforward by checking adjacent elements.

```java
import java.util.Arrays;

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

        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        
        int oddCount = 0;
        int currentCount = 0;
        
        for (int i = 0; i < chars.length; i++) {
            currentCount++;
            if (i + 1 == chars.length || chars[i] != chars[i+1]) {
                if (currentCount % 2 != 0) {
                    oddCount++;
                }
                currentCount = 0;
            }
        }
        
        return oddCount <= k;
    }
}
```
### Algorithm
- First, handle the edge case: if `k > s.length()`, it's impossible to create `k` non-empty strings. Return `false`.
- Convert the input string `s` into a character array.
- Sort the character array. This groups identical characters together.
- Iterate through the sorted array to count the frequency of each character. A single pass is sufficient.
- While iterating, maintain a count of characters that have an odd frequency (`odd_count`).
- Finally, check if `odd_count <= k`. If it is, return `true`; otherwise, return `false`.

## Optimal Approach using Frequency Array
This is the most efficient approach. It uses a frequency array (acting as a hash map) to count character occurrences in a single pass. This avoids the overhead of sorting and provides a linear time solution with constant extra space.
**Time:** O(N), where N is the length of the string `s`. We iterate through the string once to build the frequency map (O(N)), and then iterate through the map, which is constant size 26 (O(1)). · **Space:** O(1). We use a frequency array of size 26, which is constant space regardless of the input string's length. The input string itself is not counted as auxiliary space.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Simple and efficient to implement.
**Cons:** There are no significant cons to this approach as it is optimal.
### Explanation
The logical foundation of this approach is the same as the previous one. The possibility of constructing `k` palindromes hinges on two conditions:
1. The total number of characters must be sufficient to form `k` non-empty strings, i.e., `s.length() >= k`.
2. The number of characters with odd frequencies (`odd_count`) must not exceed `k`, because each requires a separate palindrome to be its center, i.e., `odd_count <= k`.

The key improvement here is the method of counting frequencies. Instead of sorting, we use a fixed-size array to store the counts of each character. Since the input string consists of lowercase English letters, an array of size 26 is sufficient.

```java
class Solution {
    public boolean canConstruct(String s, int k) {
        int n = s.length();
        if (n < k) {
            return false;
        }
        
        int[] freq = new int[26];
        for (int i = 0; i < n; i++) {
            freq[s.charAt(i) - 'a']++;
        }
        
        int oddCount = 0;
        for (int count : freq) {
            if (count % 2 != 0) {
                oddCount++;
            }
        }
        
        return oddCount <= k;
    }
}
```
### Algorithm
- First, check the preliminary condition: if `s.length() < k`, it's impossible to form `k` non-empty strings, so return `false`.
- Initialize an integer array `freq` of size 26 to all zeros. This array will store the frequency of each letter from 'a' to 'z'.
- Iterate through the string `s`. For each character `c`, increment the corresponding counter in the `freq` array (`freq[c - 'a']++`).
- Initialize a counter `odd_count` to 0.
- Iterate through the `freq` array. For each frequency `f`, if `f` is odd (`f % 2 != 0`), increment `odd_count`.
- Finally, return `true` if `odd_count <= k`, and `false` otherwise.

# Solutions
### Java

```java
class Solution {
public
  boolean canConstruct(String s, int k) {
    int n = s.length();
    if (n < k) {
      return false;
    }
    int[] cnt = new int[26];
    for (int i = 0; i < n; ++i) {
      ++cnt[s.charAt(i) - 'a'];
    }
    int x = 0;
    for (int v : cnt) {
      x += v & 1;
    }
    return x <= k;
  }
}

```

### CPP

```cpp
class Solution { public: bool canConstruct ( string s , int k ) { if ( s . size () < k ) { return false ; } int cnt [ 26 ]{}; for ( char & c : s ) { ++ cnt [ c - 'a' ]; } int x = 0 ; for ( int v : cnt ) { x += v & 1 ; } return x <= k ; } };
```

### Python

```python
class Solution:
    def canConstruct(self, s: str, k: int) -> bool: if len(s) < k: return False cnt = Counter(s) return sum(v & 1 for v in cnt . values()) <= k

```