1400. Construct K Palindrome Strings - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Construct K Palindrome Strings – Given a string s and an integer k, determine if it's possible to rearrange all the characters of s into exactly k non-empty palindrome strings. Each character from s must be used exactly once across the k palindromes. Return true if such a construction is possible, otherwise return false.

A palindrome is a string that reads the same forwards and backwards (e.g., "level" or a single character like "a").
You must use all characters of s to form the k palindromes (no characters left unused).
Each of the k strings must be non-empty.

Examples:

Example 1:
Input: s = "annabelle", k = 2
Output: true
Explanation: We can rearrange "annabelle" into 2 palindromes. For example, one valid construction is "anbna" and "elle". Both are palindromic and use all letters of s.
Example 2:
Input: s = "leetcode", k = 3
Output: false
Explanation: It is impossible to use all characters of "leetcode" to form 3 palindromic strings. (Intuition: "leetcode" has too many characters with odd counts to distribute into only 3 palindromes.)
Example 3:
Input: s = "true", k = 4
Output: true
Explanation: The string "true" has 4 characters and k = 4, so we can put each character in its own palindrome string: "t", "r", "u", "e". Single-character strings are palindromes, and all characters are used.

Constraints:

1 <= s.length <= 10^5
s consists of lowercase English letters ('a'-'z' only).
1 <= k <= 10^5

Hints Before the Solution

Hint 1: Think about the properties of a palindrome. How do character counts (frequency of each letter) affect whether you can form a palindrome? (Recall: In a palindrome, at most one character can have an odd count — this would be the middle character. All other characters must appear an even number of times to be mirrored around the center.)
Hint 2: What is the minimum number of palindromic strings you would need given the characters in s? Consider the count of characters that appear an odd number of times. Each such character can potentially be the center of a different palindrome.
Hint 3: What is the maximum number of palindrome strings you could form from s? (Think about extreme cases: you could put each character in its own palindrome, which would give you as many palindromes as the length of s.) Use these insights to establish conditions for when forming k palindromes is possible or impossible.

Multiple Approaches

We can approach this problem in more than one way. A brute force method would try to actually construct palindromic strings or check many distributions of characters, which is not efficient for large inputs. An optimized method uses counting logic to determine the possibility in linear time. Below, we discuss both approaches:

Brute Force Approach

Idea: A naive approach would be to try distributing the characters of s into k groups and check if each group can form a palindrome. This could involve generating all possible ways to partition the characters or greedily assigning characters to palindromes one by one. While this approach is conceptually straightforward, it is extremely inefficient due to the exponential number of ways to arrange characters into k sets. It’s useful for understanding the problem, but it won’t work in practice for large strings.

In-depth reasoning: For a brute force solution, one might attempt the following:

First check simple infeasible conditions:
- If k is greater than the length of s, immediately return false (you can't create more palindromes than there are characters, since each palindrome must be non-empty).
- Count how many characters have an odd frequency in s. Let this count be oddCount. To form a palindrome, each palindrome can have at most one odd-count character (which sits in the middle). If oddCount is greater than k, then even before trying anything, it’s impossible to form k palindromes (because you would need at least oddCount palindromes to accommodate each odd-count character as a center). So if oddCount > k, return false.
If these basic checks pass, a brute force algorithm might then attempt to actually construct the palindromes:
1. Assign each character with an odd count to a different palindrome as the center character. This uses up one occurrence of each odd-count character, making their remaining counts even.
2. If there are still palindrome slots left (i.e., we have fewer odd characters than k), assign some remaining characters to start new palindromes. For instance, if after assigning odd centers we still need more palindromes (say k is larger than oddCount), we can take some characters that have even counts and split them between two palindromes. Essentially, we can take one character (which would otherwise pair up) and use it alone as the center of a new palindrome. This increases the number of palindromes by 1 while still keeping that palindrome valid.
3. Distribute all remaining characters (which should now occur in even counts) into the k palindromes by pairing them up. We can place characters in pairs to the left and right ends of any palindrome. Because all leftover characters are in even counts at this point, we can always place them in symmetrical pairs. If one palindrome already has a center, we add pairs around it; if not (some palindromes might consist only of pairs with no single center), that’s fine too.
4. If we manage to use all characters in this way, then the construction is possible (return true). If at some point we cannot assign characters without breaking the palindrome property or we run out of characters before filling k palindromes, then it’s impossible (return false).

This brute force reasoning essentially mirrors the logic of the problem conditions, but actually implementing it by checking all combinations would be prohibitively slow. The number of ways to split n characters into k palindromic groups grows combinatorially with n. However, we can simulate the process in a greedy manner as described above, which is closer to an optimal solution in complexity (even though we described it here as a "brute force" thought experiment).

Brute Force Example:
Imagine s = "aabbcc" and k = 3. A brute force method would consider ways to split these 6 characters into 3 groups and check palindrome validity. One possible grouping is: {"a","b","ccba"} (which corresponds to palindromes "a", "b", "accba"). But trying all groupings is impractical. Instead, using the greedy assignment:

Count odd frequencies: here all characters a, b, c appear 2 times (even), so oddCount = 0.
We need 3 palindromes and have 0 odd-count chars. Since oddCount (0) <= k (3) and length 6 >= 3, it might be possible. We can create 3 palindromes by intentionally breaking some pairs. For example, take one a for palindrome1, one b for palindrome2, one c for palindrome3 as centers (now each of those characters has 1 left, making them odd-count in leftovers). Then distribute the remaining a, b, c as pairs around any palindrome. We could end up with palindromes like: "a", "b", "cabc" (where "cabc" is a palindrome "cab c" with center 'a' and 'c'/'b' paired around it). This is just one possibility to illustrate assignment. The brute force approach would attempt all such combinations of assignments.

Due to the complexity of brute force, let's provide a conceptual Java implementation for the checking part (the greedy assignment) to illustrate the idea. This implementation will construct palindromes in a greedy way as described, which works for the purpose of deciding true/false, but keep in mind it's simulating a "brutish" approach rather than enumerating all possibilities:

Java

. . . .

Explanation: In this brute-force style solution, we use a HashMap to count character frequencies (which is straightforward but has overhead). We then compute the number of odd-frequency characters by iterating over the map. Finally, we apply the two critical checks: if s.length < k or if oddCount > k, we return false; otherwise, return true. This solves the problem for all practical purposes. The actual "brute force" enumeration of palindromic groupings is avoided by using the character count logic to conclude the result directly (which is the key insight to optimize this problem).

Time Complexity: The above implementation runs in O(n) time for counting characters (where n is the length of the string) plus O(U) to count odds (where U is the number of unique characters, at most 26 in this case). This is effectively O(n). However, a true brute force approach that attempts to try all partitions would be exponential (O(k^n) or worse) and not feasible. By leveraging counting instead of actual permutation/partitioning, we avoided the exponential blow-up.

Space Complexity: The HashMap uses O(U) space for character counts, which in worst case is O(26) = O(1) space since the alphabet size is fixed. The overhead for storing counts is negligible for English letters. (If we considered extended character sets or if we used recursion for brute force, space could grow differently, but in this counting method it’s constant relative to input size.)

Python Code

Python3

. . . .

Optimized Approach

Idea: The optimized solution uses the insights from character counts directly, without any unnecessary overhead or brute force search. We can determine the answer by just looking at the counts of characters in s:

If k is greater than the length of s, return false immediately (too many palindromes needed).
Count the number of characters with odd frequency (oddCount). Each palindrome can accommodate at most one odd-count character (as its center). Therefore, if oddCount > k, return false.
Otherwise (if oddCount <= k <= n), return true. This condition essentially means we have enough palindromes to assign each odd character to its own palindrome (or some palindromes will have no odd center and consist entirely of paired characters), and we do not require more palindromes than available characters.

This approach is greedy by logic, not by trial and error: it identifies the necessary conditions and immediately concludes the result. We don't actually construct the palindromes; we just verify they could be constructed.

Efficient Implementation: We can implement the above logic very efficiently in one pass using an array or bit manipulation to count character frequencies. Since we only care about odd or even counts (parity of counts), we can even use a single integer as a bit mask to track odd/even counts for each letter. Here's an optimized Java implementation:

Java Code

Java

. . . .

In this optimized code:

We first handle the edge case n < k.
We then use a bit mask (mask) to accumulate parity of counts. We iterate over each character in s and flip the corresponding bit. If a character appears an even number of times, its bit will end up 0 (flipped an even number of times), and if it appears an odd number of times, its bit will end up 1.
We count the number of 1 bits in mask using Integer.bitCount(mask), which gives us oddCount.
Finally, we check that oddCount <= k. (We already know k <= n from the earlier check, so if oddCount <= k, then k is automatically <= n or equal, so the conditions oddCount <= k <= n are satisfied.)

Space Optimization: This approach is memory-efficient. Instead of using a HashMap or even an array of size 26, we used a single integer (mask) to store 26 bits of information about character counts. This is a constant space solution (O(1) space, since the alphabet is fixed). If using an array of length 26 for counts, that’s also O(1) space in terms of Big-O notation. In practice, the difference between using an array and an integer bit mask is minor in memory, but the bit mask is a neat trick to reduce space and possibly improve speed slightly by using bitwise operations.

Time Complexity: This optimized solution runs in O(n) time, where n is the length of the string. We make one pass through the string to build the bit mask (or count array), and then do O(1) work to count bits and compare with k. Counting bits in a 32-bit number is constant time. Overall, this is linear time, which is optimal for this problem since we must look at each character at least once.

Space Complexity: O(1) as explained (only a fixed number of variables and at most 26 counters or bits, regardless of input size).

Python Code

Python3

. . . .

Step-by-Step Walkthrough

Let's walk through the solution logic with a visual example to solidify the understanding. Consider s = "annabelle" and k = 2 (from Example 1):

Step 1: Count characters.
The string "annabelle" has 9 characters. Counting frequencies:
- a: 2
- n: 2
- b: 1
- e: 2
- l: 2
  (Characters that are not in the string have count 0, which we can ignore.)
  Total length n = 9.
Step 2: Check length vs k.
Here n = 9 and k = 2. Since n >= k (9 >= 2), it's potentially possible to form 2 palindromes (we have enough characters to distribute at least one per palindrome). If instead k were greater than 9, it would be immediately impossible. (For example, if k = 10 but we only have 9 characters, we can't create 10 non-empty strings.)
Step 3: Count odd-frequency characters.
In the counts above, which characters have an odd count?
- a: 2 (even)
- n: 2 (even)
- b: 1 (odd)
- e: 2 (even)
- l: 2 (even)
  There is exactly 1 odd-count character (b appears once). So oddCount = 1.
Step 4: Check oddCount vs k.
We found oddCount = 1. We have k = 2 palindromes to form. Since oddCount <= k (1 <= 2), it means it's feasible to distribute the odd-count characters across the palindromes. In fact, we only have one odd character (b), so at minimum we need 1 palindrome to accommodate it (as its center). We have 2 palindromes to use, which is plenty for this one odd character. This condition indicates no obvious obstacle in terms of odd characters. If instead we had, say, 3 odd-count characters but still only k = 2 palindromes, it would be impossible (because at least one palindrome would need to contain two odd-count characters, which can't happen as they would conflict for the center position).
Step 5: Conclusion for example.
Both conditions passed: (a) 9 >= 2 and (b) 1 <= 2. Therefore, the algorithm will return true — it is possible to construct 2 palindrome strings from "annabelle".
To verify, one actual construction is: "anbna" and "elle". Let's see how this uses all characters:
- "anbna" is a palindrome (reads the same backwards). Here, 'b' is the center (odd-count char in this palindrome) and "a" and "n" letters are placed symmetrically around 'b'. It uses 2 a's, 2 n's, and 1 b.
- "elle" is a palindrome composed of "e" and "l". It uses 2 e's and 2 l's (both letters have even count and form a symmetric string). Together, these palindromes use all letters {a, a, n, n, b, e, e, l, l}. The odd-count letter 'b' was placed in its own palindrome center, and all other letters (with even counts) were arranged in either the first or second palindrome as pairs.
Another example walkthrough: Take s = "leetcode" and k = 3 (Example 2 which should return false):
- Count characters: "leetcode" = 8 letters. Frequency: l:1, e:3, t:1, c:1, o:1, d:1.
- n = 8, k = 3. Here n (8) >= k (3), so length is not the issue.
- Count odd frequencies: l(1), e(3), t(1), c(1), o(1), d(1). That’s actually 6 characters with odd counts (notice e = 3 is odd, and five other letters appear once). So oddCount = 6.
- Check oddCount vs k: 6 > 3. We have 6 odd-count characters but only 3 palindromes to place them in. This means at least 3 palindromes would not be enough because at best, 3 palindromes could accommodate 3 odd-count centers, but we have 6 that need to be placed. The condition fails here. So the algorithm returns false. This matches our expectation — it's impossible to rearrange "leetcode" into 3 palindromic strings. No matter how you try, you'd always end up with some palindrome needing to contain two of those odd letters, which can't form a palindrome properly. (For instance, you might try grouping letters, but you'd find a violation of the palindrome property in any grouping.)
Edge case example: s = "true", k = 4:
- Count characters: t:1, r:1, u:1, e:1 (each letter appears once, all odd counts). n = 4.
- n (4) >= k (4), okay.
- oddCount = 4 (since all 4 characters have odd count 1).
- oddCount (4) <= k (4), okay (they're equal, which is fine — it means we have exactly 4 odd chars and 4 palindromes, so likely each palindrome will just take one of these odd chars as center).
- The algorithm returns true. And indeed, the only way to use all characters in 4 palindromes is to put each character by itself: "t", "r", "u", "e". Each of these is a palindrome of length 1. This example shows that when k equals the string length, the answer is always true (each character can stand alone). It also shows that having every character with an odd count is fine as long as k is at least that number (here k was exactly equal to the number of odd characters).

The step-by-step process highlights that the core checks are:

Are there enough characters to distribute into k palindromes? (Length check)
Are there too many odd-frequency characters to fit into k palindromes? (Odd count check)
If both conditions are satisfied, the answer is Yes (true); otherwise No (false).

##. Common Mistakes & Edge Cases

Common Pitfalls:

Ignoring the length condition (k <= s.length): Forgetting to check that you have at least as many characters as palindromes. If k is larger than the number of characters, it's impossible to form k non-empty strings. This is a simple but crucial check.
Misunderstanding the odd character distribution: A frequent mistake is thinking that if the number of odd-count characters is not exactly equal to k, then it’s impossible. The correct condition is oddCount <= k, not necessarily equal. For example, if s = "aabb" (no odd counts) and k = 3, it's still possible to form 3 palindromes ("a", "a", "bb") by breaking some even counts into singletons. So if there are fewer odd characters than k, the extras can always be accommodated by splitting some even-count pairs into separate palindromes. The only time it's impossible is when oddCount > k (too many odd chars) or k > n (not enough chars).
Assuming you always need to use every palindrome slot for an odd character: You can have palindromes that consist entirely of paired characters and no center odd character. For instance, if s = "aabbcc" and k = 2, you have 0 odd-count chars but k=2; you can still form 2 palindromes (e.g., "abcba" and "c", or other distributions). One palindrome might take a center even though it wasn't strictly needed from an odd-count perspective. The key is that as long as oddCount <= k, any "extra" palindromes beyond the oddCount can be formed by splitting even counts or using single characters as needed.
Not accounting for single-character palindromes: Remember that a single character by itself is a valid palindrome. So it's perfectly fine (and sometimes necessary) to have palindromes of length 1. This often occurs in cases where k is large or close to the string length.
Mixing up conditions: Some might incorrectly require both oddCount == k and k == n or other stricter conditions. The conditions are independent: you need k <= n and oddCount <= k. If those hold, it's enough. There is no need for oddCount to equal k or any specific relationship beyond <=. Many different scenarios fit these conditions.

Edge Cases to Consider:

k equals n: As noted, this scenario means each character must be its own palindrome. This is always possible as long as k <= n (which in this case is equality), because each character can stand alone. E.g., s = "abc", k = 3 -> true (["a","b","c"]).
k = 1: We need to use all characters in one palindrome. This is possible if and only if s itself can be rearranged into a palindrome. That means at most one character can have an odd count. For example, s = "carerac", k = 1 -> true (it's an anagram of "racecar"), but s = "abc", k = 1 -> false (you can't form a single palindrome that uses all three different letters).
All characters same: If s = "aaaaaa" (all one letter), you can form any k up to n palindromes. If k = n, it's each "a". If k is smaller, you can bunch some together (e.g., k=1 would be the entire string "aaaaaa", which is itself a palindrome). As long as k <= n, it will be true. This is a good sanity check for the condition: oddCount in this case is either 0 (if length is even) or 1 (if length is odd), which will always be <= k as long as k <= n.
Too many palindromes requested: If k > n, immediately false. Example: s = "abc", k = 5 -> false, because you only have 3 characters and you can't form 5 non-empty strings.
Too many odd counts: As discussed, if oddCount > k, it's false. Example: s = "aaaabb" (which has oddCount = 2: 'a' appears 4 times (even), 'b' appears 2 times (even) – actually oddCount = 0 in this example, let's pick another) say s = "aaabbbcc" (counts: a:3, b:3, c:2; oddCount=2 for a and b) and let k = 1; then it's false because you can't put two different odd-count letters into one palindrome.
String length 1: If s has length 1, then:
- If k = 1, it's true (the single character is a palindrome by itself).
- If k > 1, it's false (you can't form more than one palindrome from a single character).

By carefully checking these edge cases with the conditions, you'll see the rules hold up.

Related LeetCode Problems for Further Practice:

Palindrome Permutation (LeetCode 266): Given a string, determine if any permutation of it can form a palindrome. This is essentially the k = 1 case of our problem. The solution is to check that at most one character has an odd count (very similar logic to what we used).
Palindrome Permutation II (LeetCode 267): Given a string, return all distinct palindromic permutations of it. This goes a step further than just checking possibility (like 266); it actually asks to generate the palindromes. It requires using half the palindrome and backtracking to form all unique permutations.
Longest Palindrome (LeetCode 409): Here you are not obligated to use all characters, but instead you want to form the longest palindrome you can from the letters of s. The greedy solution is to use all pairs of characters (even counts) and at most one odd as center. It's related by the use of counting odd/even frequencies.
Palindrome Partitioning (LeetCode 131) / Palindrome Partitioning II (LeetCode 132): These problems involve partitioning a given string into palindromic substrings. Note that in these problems, you cannot rearrange characters; you must cut the string in order. They are solved with backtracking or dynamic programming and are a different scenario from our problem (which allows rearrangement of characters freely).

Variations of the Problem:

Construct at most k palindrome strings: If the problem allowed using all characters in at most k palindromes (i.e. up to k, not exactly k), the answer would always be true when k is greater than or equal to the minimum needed palindromes. Since the minimum needed is the number of odd-count characters, as long as k is >= that number, you could choose to use exactly that many palindromes and ignore the rest (or consider the rest empty, which isn't allowed in original problem but would be moot if it's "at most"). Essentially, the interesting constraint is when it’s exactly k. The exact k condition forces you to use all palindromes, which is a harder constraint than at most k.
Actually constructing the palindromic strings: Our problem only asks for a yes/no answer. If a variation asked you to actually output one possible set of k palindromes (assuming it’s possible), you would need to extend the greedy approach to distribute characters into palindromes. As discussed in the brute force approach, one can greedily assign odd-count chars as centers, then distribute remaining pairs. Implementing this would be more involved but follows naturally from the counting logic. This could be a good exercise in greedy construction once the yes/no logic is clear.
Different character sets: If the string included uppercase letters or other types of characters, the approach remains the same — just the frequency counting would extend to a larger character set (for example, 52 letters for both cases or even all Unicode). The complexity would be O(n + C) where C is the size of the character set. The bit-mask trick works nicely for small fixed alphabets (like 26 lowercase letters). For larger sets, using a HashMap or array would be fine.
Requiring palindromes to be distinct or other additional constraints: The current problem has no requirement that the k palindromes be unique or any particular length. A variation could ask for distinct palindromes or minimize/maximize something, which would complicate matters and likely require different techniques (maybe backtracking or additional combinatorial logic). Our problem is simpler – it only asks about existence of some valid construction.

1400. Construct K Palindrome Strings - Detailed Explanation

Problem Statement

Hints Before the Solution

Multiple Approaches

Brute Force Approach

Python Code

Optimized Approach

Java Code

Python Code

Step-by-Step Walkthrough

Alternative Variations & Related Problems