Construct K Palindrome Strings

medium string counting greedy

Problem

Given a string s and an integer k, return true if you can use all the characters in s to construct exactly k non-empty palindrome strings, and false otherwise. A palindrome can hold at most one character whose count is odd (it sits in the middle), so the answer hinges on how many letters appear an odd number of times.

Inputs = "annabelle", k = 2

Outputtrue

Letter b is the only one with an odd count, so 1 odd letter ≤ k = 2 palindromes (e.g. "anna" + "elble").

s (lowercase letters)

def canConstruct(s, k):
    # Need at least k characters to fill k non-empty strings.
    if len(s) < k:
        return False
    count = {}
    for ch in s:                       # tally each letter
        count[ch] = count.get(ch, 0) + 1
    odd = 0
    for v in count.values():           # count odd-frequency letters
        if v % 2 == 1:
            odd += 1
    # Each palindrome absorbs at most one odd-count letter (its center).
    return odd <= k

function canConstruct(s, k) {
  // Need at least k characters to fill k non-empty strings.
  if (s.length < k) return false;
  const count = {};
  for (const ch of s) {                 // tally each letter
    count[ch] = (count[ch] || 0) + 1;
  }
  let odd = 0;
  for (const v of Object.values(count)) { // count odd-frequency letters
    if (v % 2 === 1) odd++;
  }
  // Each palindrome absorbs at most one odd-count letter (its center).
  return odd <= k;
}

boolean canConstruct(String s, int k) {
    // Need at least k characters to fill k non-empty strings.
    if (s.length() < k) return false;
    int[] count = new int[26];
    for (char ch : s.toCharArray())       // tally each letter
        count[ch - 'a']++;
    int odd = 0;
    for (int v : count)                   // count odd-frequency letters
        if (v % 2 == 1) odd++;
    // Each palindrome absorbs at most one odd-count letter (its center).
    return odd <= k;
}

bool canConstruct(string s, int k) {
    // Need at least k characters to fill k non-empty strings.
    if ((int)s.size() < k) return false;
    int count[26] = {0};
    for (char ch : s)                     // tally each letter
        count[ch - 'a']++;
    int odd = 0;
    for (int v : count)                   // count odd-frequency letters
        if (v % 2 == 1) odd++;
    // Each palindrome absorbs at most one odd-count letter (its center).
    return odd <= k;
}

Explanation

The key insight is what makes a string a palindrome: every character must appear an even number of times, except possibly one character that sits exactly in the middle. So a single palindrome can "absorb" at most one letter that occurs an odd number of times.

That turns the whole question into pure counting. Tally the frequency of every letter in s, then count how many letters have an odd frequency — call this odd. Each of those odd letters needs its own palindrome center, so we need at least odd palindromes.

There are two ways the answer is false. First, if s.length < k we simply don't have enough characters to fill k non-empty strings. Second, if odd > k we have more "must-be-center" letters than palindromes to host them.

Otherwise the answer is true. When odd <= k <= len(s), we can always build exactly k palindromes: give each odd letter its own center, distribute the rest in even pairs, and if we still have fewer than k strings, peel single characters off (a single character is itself a palindrome) until we reach k.

Example: "annabelle" has counts a:2, n:2, b:1, e:2, l:2. Only b is odd, so odd = 1 ≤ k = 2 and the length 9 ≥ 2 — the answer is true.

Time: O(n) Space: O(1) (26 letters)