Construct K Palindrome Strings

Med

#1296Time: 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.

Patterns

Greedy Counting

Data structures

Hash Table String

Prompt

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 <= 10⁵
s consists of lowercase English letters.
1 <= k <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.Arrays;2 3class Solution {4    public boolean canConstruct(String s, int k) {5        if (s.length() < k) {6            return false;7        }8        9        if (s.length() == k) {10            return true;11        }12 13        char[] chars = s.toCharArray();14        Arrays.sort(chars);15        16        int oddCount = 0;17        int currentCount = 0;18        19        for (int i = 0; i < chars.length; i++) {20            currentCount++;21            if (i + 1 == chars.length || chars[i] != chars[i+1]) {22                if (currentCount % 2 != 0) {23                    oddCount++;24                }25                currentCount = 0;26            }27        }28        29        return oddCount <= k;30    }31}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

The logical foundation of this approach is the same as the previous one. The possibility of constructing k palindromes hinges on two conditions:

The total number of characters must be sufficient to form k non-empty strings, i.e., s.length() >= k.
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.

1class Solution {2    public boolean canConstruct(String s, int k) {3        int n = s.length();4        if (n < k) {5            return false;6        }7        8        int[] freq = new int[26];9        for (int i = 0; i < n; i++) {10            freq[s.charAt(i) - 'a']++;11        }12        13        int oddCount = 0;14        for (int count : freq) {15            if (count % 2 != 0) {16                oddCount++;17            }18        }19        20        return oddCount <= k;21    }22}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  boolean canConstruct(String s, int k) {4    int n = s.length();5    if (n < k) {6      return false;7    }8    int[] cnt = new int[26];9    for (int i = 0; i < n; ++i) {10      ++cnt[s.charAt(i) - 'a'];11    }12    int x = 0;13    for (int v : cnt) {14      x += v & 1;15    }16    return x <= k;17  }18}

1class 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 ; } };

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem