Problem Description

Given a string s and an integer k, determine if it is possible to construct k non-empty palindrome strings using all the characters in s exactly once. Each character must be used in exactly one palindrome, and each palindrome must be non-empty. You may rearrange the characters in s as needed.

• Return true if it is possible to construct exactly k palindrome strings as described, otherwise return false.
• Key constraints:
  • Each character in s must be used exactly once.
  • No character may be reused or omitted.
  • Each palindrome must be non-empty.
  • There is no requirement to output the actual palindromes, just to determine if it is possible.

Thought Process

To solve this problem, we need to understand what makes a string a palindrome and how to partition a set of characters into palindromes. The brute-force way would be to try every possible partition of the characters into k groups and check if each group forms a palindrome, but this is computationally infeasible for larger strings.

Instead, we notice that the key property of a palindrome is that at most one character can have an odd count (for odd-length palindromes), and all others must have even counts. For k palindromes, the minimum number of palindromes we need is at least the number of characters with odd counts, because each such character must be the center of some palindrome.

So, the problem reduces to counting the number of characters with odd frequencies, and checking whether it's possible to create k palindromes given this constraint.

Solution Approach

• Step 1: Count the frequency of each character in s. This can be done using a hash map or array.
• Step 2: Count how many characters have odd frequencies. Let's call this odd_count.
• Step 3: Analyze the constraints:
  • We need at least odd_count palindromes, because each odd-count character must be the center of a palindrome.
  • We cannot create more palindromes than the total number of characters, so k must be less than or equal to len(s).
• Step 4: If odd_count ≤ k ≤ len(s), return true; otherwise, return false.

We use a hash map for counting because it allows O(1) lookups and updates for each character. This makes the solution efficient and straightforward.

Example Walkthrough

Example: s = "annabelle", k = 2

1. Count character frequencies:
   • 'a': 2
   • 'n': 2
   • 'b': 1
   • 'e': 2
   • 'l': 2
2. Characters with odd counts: only 'b' occurs once (odd_count = 1).
3. Check constraints:
   • odd_count = 1
   • k = 2
   • len(s) = 8

   Since odd_count ≤ k ≤ len(s) (1 ≤ 2 ≤ 8), it is possible to construct 2 palindrome strings using all characters.

Another Example: s = "leetcode", k = 3
Frequencies: l:1, e:3, t:1, c:1, o:1, d:1
Odd-count characters: l, t, c, o, d (each 1), e (3): so 6 odd-count characters.
Since odd_count = 6 and k = 3, and 6 > 3, it is not possible.

Code Implementation

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if k > len(s):
            return False
        from collections import Counter
        freq = Counter(s)
        odd_count = sum(1 for v in freq.values() if v % 2 == 1)
        return odd_count <= k
      

class Solution {
public:
    bool canConstruct(string s, int k) {
        if (k > s.size()) return false;
        vector<int> freq(26, 0);
        for (char c : s) freq[c - 'a']++;
        int odd_count = 0;
        for (int f : freq) {
            if (f % 2 == 1) odd_count++;
        }
        return odd_count <= k;
    }
};
      

class Solution {
    public boolean canConstruct(String s, int k) {
        if (k > s.length()) return false;
        int[] freq = new int[26];
        for (char c : s.toCharArray()) freq[c - 'a']++;
        int odd_count = 0;
        for (int f : freq) {
            if (f % 2 == 1) odd_count++;
        }
        return odd_count <= k;
    }
}
      

var canConstruct = function(s, k) {
    if (k > s.length) return false;
    let freq = new Array(26).fill(0);
    for (let i = 0; i < s.length; i++) {
        freq[s.charCodeAt(i) - 97]++;
    }
    let odd_count = 0;
    for (let f of freq) {
        if (f % 2 === 1) odd_count++;
    }
    return odd_count <= k;
};
      

Time and Space Complexity

• Brute-force approach: Trying all partitions would be exponential in time and space, O(2^n), and is not feasible for even moderate input sizes.
• Optimized approach (as above):
  • Time complexity: O(n), where n is the length of s. We scan the string once to count frequencies, and then once more to count odd frequencies.
  • Space complexity: O(1) if we assume only lowercase letters (fixed 26), otherwise O(m) where m is the number of unique characters.

Summary

The key insight is that the minimum number of palindromes needed is equal to the number of characters with odd frequencies, since each odd-count character must be the center of a palindrome. By counting the odd frequencies and checking the constraints, we can efficiently determine if k palindrome strings can be constructed from the input. This solution is both elegant and efficient, leveraging fundamental properties of palindromes and character counts.