Construct K Palindrome Strings
MedPrompt
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 <= 105sconsists of lowercase English letters.1 <= k <= 105
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 createknon-empty strings. Returnfalse. - Convert the input string
sinto 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, returntrue; otherwise, returnfalse.
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.
import java.util.Arrays; class Solution { public boolean canConstruct(String s, int k) { if (s.length() < k) { return false; } if (s.length() == k) { return true; } char[] chars = s.toCharArray(); Arrays.sort(chars); int oddCount = 0; int currentCount = 0; for (int i = 0; i < chars.length; i++) { currentCount++; if (i + 1 == chars.length || chars[i] != chars[i+1]) { if (currentCount % 2 != 0) { oddCount++; } currentCount = 0; } } return oddCount <= k; }}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.
Solutions
Solution
class Solution {public boolean canConstruct(String s, int k) { int n = s.length(); if (n < k) { return false; } int[] cnt = new int[26]; for (int i = 0; i < n; ++i) { ++cnt[s.charAt(i) - 'a']; } int x = 0; for (int v : cnt) { x += v & 1; } return x <= 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.