Watch 10 video solutions for Construct K Palindrome Strings, a medium level problem involving Hash Table, String, Greedy. This walkthrough by NeetCodeIO has 9,542 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 105s consists of lowercase English letters.1 <= k <= 105Problem 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 | 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. |