Problem

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.

Examples

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.

Solution

Method 1- Count the occurrences of chars

Intuition 1 - We need atleast k characters in string, otherwise it is impossible to form k palindromes. Intuition 2 - Count the occurences

A string is a palindrome:

  • if it reads the same forwards and backwards.
  • ⇨ all characters must have even frequencies except at most one character which can have an odd frequency (this character will be in the middle).

So, we should count the occurrences of all the character. Now, some characters will occur odd number of times, and some even number of times.

Suppose we have one character which occurs odd number of times, then this character must be in middle of some word to form atleast 1 palindrome with odd length.

  • For example, consider "abbba". Here, we can form at least one palindrome.

Now, suppose we have two characters that appear an odd number of times.

  • For example, in the string "aabc", we will form at least two palindromes; for instance, "aba" and "c". It isn’t possible to form fewer than two palindromes.

Therefore, if we have x characters that appear an odd number of times, we would form at least x palindromes, and x should be less than or equal to k.

So, in summary number of palindromes we can form are in range [x, l], where x is the number of characters that have odd frequencies (since each of these requires a separate palindrome) and l is the length of the string (as each character can individually act as a palindrome).

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

Java
class Solution {
    public boolean canConstruct(String s, int k) {
        if (k > s.length()) {
            return false;
        }
        
        Map<Character, Integer> charFreq = new HashMap<>();
        for (char c : s.toCharArray()) {
            charFreq.put(c, charFreq.getOrDefault(c, 0) + 1);
        }
        
        int oddCount = 0;
        for (int freq : charFreq.values()) {
            if (freq % 2 != 0) {
                oddCount++;
            }
        }
        
        return oddCount <= k;
    }
}
Python
class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if k > len(s):
            return False
        
        char_freq = Counter(s)
        odd_count = sum(1 for freq in char_freq.values() if freq % 2 != 0)
        
        return odd_count <= k

Complexity

  • ⏰ Time complexity:  O(n) where n is the length of the string s. We iterate through the string once to count character frequencies and then check odd frequencies.
  • 🧺 Space complexity: O(1) for the character frequency count since the character set is fixed.