Construct K Palindrome Strings — Problem & Solution
Construct K Palindrome Strings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Construct K Palindrome Strings is a medium coding problem on strings, hash table and greedy, asked in Uber interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Greedy, Counting
- Asked at: Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s and an integer k.
Return true if you can use every character of s exactly once to build exactly k non-empty palindromes, and false otherwise. Characters may be rearranged freely across and within the palindromes.
Example 1
Input: s = "racecars", k = 2
Output: true
Explanation: `e` and `s` occur an odd number of times, and each palindrome can hold one odd letter in its middle: for example `rcecr` and `asa`.
Example 2
Input: s = "codekairo", k = 3
Output: false
Explanation: Seven letters occur once each (c, d, e, k, a, i, r), and three palindromes can hold at most three of them in their centres.
Example 3
Input: s = "abc", k = 4
Output: false
Explanation: Three characters cannot fill four non-empty strings.
Constraints
1 <= s.length <= 10^5s holds lowercase English letters1 <= k <= 10^5
Hints for Construct K Palindrome Strings
Hint 1
In a palindrome, at most one character can appear an odd number of times.
Hint 2
Count the characters of
sthat occur an odd number of times — each of them needs its own palindrome.Hint 3
Beyond that,
kpalindromes need at leastkcharacters. Are these two conditions enough?
How to solve Construct K Palindrome Strings
Each palindrome absorbs at most one odd-count character (its centre), so odd <= k is necessary; non-emptiness needs k <= |s|. Both together are also sufficient.
Approach
- Count each letter of
s. - Let
oddbe the number of letters with an odd count. - Return
odd <= k && k <= s.length.
Why it works
Necessity is clear from the two observations. For sufficiency, start with odd single-letter palindromes (one per odd letter, or one palindrome of any pair-built letters if odd is 0) and distribute the remaining letters as mirrored pairs around existing centres. While fewer than k palindromes exist, split off a new one: take one pair and form a two-letter palindrome, or a single letter from a pair — there are |s| - odd paired letters, enough to create k - odd extra non-empty palindromes when k <= |s|; splitting a pair into two singles keeps every string a palindrome.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Forgetting
k <= s.lengthreturnstruefors = "a", k = 2. - Comparing the number of distinct letters with
kis wrong — only letters with an odd count matter.
Reference solution
Python
def canConstruct(s: str, k: int) -> bool:
if k > len(s):
return False
cnt = [0] * 26
for ch in s:
cnt[ord(ch) - 97] += 1
odd = sum(c & 1 for c in cnt)
return odd <= kJava
public static boolean canConstruct(String s, int k) {
if (k > s.length()) return false;
int[] cnt = new int[26];
for (int i = 0; i < s.length(); i++) cnt[s.charAt(i) - 'a']++;
int odd = 0;
for (int c : cnt) odd += c & 1;
return odd <= k;
}C++
bool canConstruct(string s, int k) {
if (k > (int)s.size()) return false;
int cnt[26] = {0};
for (char ch : s) cnt[ch - 'a']++;
int odd = 0;
for (int c : cnt) odd += c & 1;
return odd <= k;
}JavaScript
var canConstruct = function(s, k) {
if (k > s.length) return false;
var cnt = new Array(26).fill(0);
for (var i = 0; i < s.length; i++) cnt[s.charCodeAt(i) - 97]++;
var odd = 0;
for (var j = 0; j < 26; j++) odd += cnt[j] & 1;
return odd <= k;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets