Construct K Palindrome Strings - Solution & Explanation
Problem Statement
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.
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 <= 105sconsists of lowercase English letters.1 <= k <= 105
Approach Overview
Problem Overview: You are given a string s and an integer k. The task is to determine whether you can rearrange all characters of the string to form exactly k palindrome strings. Each character must be used exactly once.
Approach 1: Character Frequency Counting (Greedy) (Time: O(n), Space: O(1))
This approach relies on a core property of palindromes: most characters must appear in pairs, while at most one character in each palindrome can have an odd frequency. Start by counting the frequency of each character using a fixed-size array or hash table. Then count how many characters have odd frequencies. Each odd-frequency character must serve as the center of a palindrome. If the number of odd counts is greater than k, constructing k palindromes is impossible. Also check that len(s) >= k, since every palindrome needs at least one character. This greedy check works because paired characters can always be distributed across palindromes while odd characters determine the minimum number of palindromes required.
Approach 2: Direct Construction Simulation (Time: O(n), Space: O(1) to O(26))
This method simulates how palindromes would actually be built. First compute character frequencies from the string. Assign each odd-frequency character as the center of a palindrome. If the number of such centers exceeds k, construction fails immediately. Otherwise, distribute remaining characters in pairs across the palindromes. Because palindromes mirror characters on both sides, pairs can be added to any existing palindrome without breaking the structure. The algorithm effectively mimics the greedy reasoning while explicitly managing palindrome construction using greedy allocation of pairs.
Recommended for interviews: Character Frequency Counting is the expected solution. Interviewers want you to recognize the palindrome property that odd frequencies determine the minimum number of palindromes. The implementation is short, runs in O(n) time, and uses constant space due to the limited alphabet. The simulation approach demonstrates deeper understanding of palindrome structure but introduces unnecessary steps compared to the direct greedy condition check.
Approach 1: Approach 1: Character Frequency Counting
This approach revolves around counting the frequency of each character in the input string. A valid palindrome can contain at most one character with an odd frequency. Hence, if the number of characters with odd frequencies is greater than k, it is impossible to create k palindrome strings. If it is less than or equal to k, constructing the palindromes is feasible.
We count each character's frequency in the string. Then, we count how many characters have odd frequencies. If the number of such odd frequencies is greater than k, it's impossible to form k palindromes, so we return false. Otherwise, we return true.
Complexity
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as we use a fixed-size array (26 for lowercase letters).
Approach 2: Approach 2: Direct Construction Simulation
This approach seeks a practical simulation of constructing k palindrome strings from the given input string. The idea is to simulate the creation of palindromes in real-time by matching characters from the frequency counts and envisioning the formation of iterative palindromes based on availability and requirement.
The algorithm directly counts and integrates odd character occurrences to match them with palindromic needs based on given k, deducing the solution by logically partitioning the string for potential palindromes.
Complexity
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as it relies on a predefined array to track character counts effectively.
Approach 3: Counting
First, we check if the length of string s is less than k. If it is, we cannot construct k palindrome strings, so we can directly return false.
Otherwise, we use a hash table or an array cnt to count the occurrences of each character in string s. Finally, we only need to count the number of characters x that appear an odd number of times in cnt. If x is greater than k, we cannot construct k palindrome strings, so we return false; otherwise, we return true.
The time complexity is O(n), and the space complexity is O(C). Where n is the length of string s, and C is the size of the character set, here C=26.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Character Frequency Counting | Time Complexity: O(n), where n is the length of the string. |
| Approach 2: Direct Construction Simulation | Time Complexity: O(n), where n is the length of the string. |
| Counting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Character Frequency Counting (Greedy) | O(n) | O(1) | Best general solution. Quickly checks palindrome feasibility using odd frequency counts. |
| Direct Construction Simulation | O(n) | O(1) to O(26) | Useful for understanding how characters are distributed when forming palindromes. |
Video Solution
Construct K Palindrome Strings - Leetcode 1400 - Python • NeetCodeIO • 9,692 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Construct K Palindrome Strings easy or hard?
Construct K Palindrome Strings Python/Java solution
How to solve Construct K Palindrome Strings in O(n)?
What is the best approach for Construct K Palindrome Strings?
Is Construct K Palindrome Strings asked at Google/Amazon/Meta?
What data structure is used in Construct K Palindrome Strings?
What is the time complexity of Construct K Palindrome Strings?
Ready to solve this problem?
Practice Construct K Palindrome Strings with our built-in code editor and test cases.
Practice on FleetCode