Construct K Palindrome Strings

Medium
1785.

Construct K Palindrome Strings

Construct K Palindrome Strings is a medium coding problem on strings, hash table and greedy, asked in Uber interviews.

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^5
  • s holds lowercase English letters
  • 1 <= k <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {boolean}
 */
var canConstruct = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • s holds lowercase English letters
  • 1 <= k <= 10^5

Hints for Construct K Palindrome Strings

  1. Hint 1

    In a palindrome, at most one character can appear an odd number of times.

  2. Hint 2

    Count the characters of s that occur an odd number of times — each of them needs its own palindrome.

  3. Hint 3

    Beyond that, k palindromes need at least k characters. 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

  1. Count each letter of s.
  2. Let odd be the number of letters with an odd count.
  3. 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.length returns true for s = "a", k = 2.
  • Comparing the number of distinct letters with k is 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 <= k

Java

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