Construct K Palindrome Strings: Counting Odd Frequencies

Given a string s and an integer k, return true if you can use all the characters of s to construct exactly k palindrome strings. Every character must be used, and each palindrome must contain at least one character.

This is LeetCode 1400: Construct K Palindrome Strings, a medium problem that tests whether you truly understand the structure of palindromes. The solution is surprisingly short once you see the key insight.

Why this problem matters

Most palindrome problems ask you to build or find a palindrome. This one flips the question: can you partition a string into exactly k palindromes using every character? It forces you to think about what makes a palindrome possible in the first place, not just how to check if a string is one.

The insight you build here, that odd-frequency characters are the bottleneck, shows up in problems like "Longest Palindrome" (LeetCode 409), "Palindrome Permutation" (LeetCode 266), and any problem that involves rearranging characters into palindromic structures.

The key insight

A palindrome can have at most one character with an odd frequency. That character sits in the center. Every other character must appear an even number of times so it can be mirrored on both sides.

If you count the characters in s and find that odd_count characters have odd frequencies, then you need at least odd_count palindromes. Each of those odd-frequency characters needs its own palindrome to serve as a center. You cannot stuff two odd-frequency characters into the same palindrome, because a palindrome only has one center.

There is also an upper bound. You cannot form more palindromes than you have characters. Each palindrome needs at least one character, so k cannot exceed len(s).

Combining both constraints, the answer is simply: odd_count is at most k, and k is at most len(s).

The solution

from collections import Counter

def can_construct(s: str, k: int) -> bool:
    if k > len(s):
        return False
    odd_count = sum(1 for count in Counter(s).values() if count % 2 == 1)
    return odd_count <= k

This is the entire solution. Let's break down what each piece does.

The first check handles the upper bound. If k exceeds the length of s, you cannot form k non-empty strings from len(s) characters. Return False immediately.

The Counter(s) call counts the frequency of every character. Then we count how many of those frequencies are odd. This is odd_count, the number of characters that need a palindrome center.

The final return checks the lower bound. If odd_count is at most k, we have enough palindromes to accommodate every odd-frequency character. The even-frequency characters can be split freely across any palindrome, so they never cause a problem.

Visual walkthrough

Let's trace through s = "annabelle" with two different values of k to see how the condition works.

The condition odd_count is at most k is at most len(s) captures everything. You do not need to actually construct the palindromes. You just need to verify that it is feasible.

Complexity analysis

Time is O(n) where n is the length of s. You scan the string once to count character frequencies, then iterate over at most 26 entries (lowercase English letters) to count odd frequencies.

Space is O(1) because the frequency counter holds at most 26 keys. The space does not grow with the input size.

Building blocks

1. Character frequency counting

The pattern of using a hash map to count character occurrences:

from collections import Counter

freq = Counter(s)

This is the same building block used in "Valid Anagram," "Group Anagrams," "Longest Palindrome," and dozens of other string problems. Whenever a problem asks about character distributions, rearrangements, or matching, frequency counting is usually the first step.

2. Odd-frequency analysis

The pattern of checking how many characters have odd frequencies:

odd_count = sum(1 for count in freq.values() if count % 2 == 1)

This specific check appears in palindrome construction problems repeatedly. A string can be rearranged into a palindrome if and only if at most one character has an odd frequency. This problem generalizes that rule to k palindromes: at most k characters can have odd frequencies.

Edge cases

Before submitting, think through these scenarios:

• k equals len(s): every character becomes its own single-character palindrome. Always returns true, since each single character is trivially a palindrome and odd_count can never exceed len(s).
• k equals 1: you are asking if the entire string can be rearranged into one palindrome. This is true if and only if at most one character has an odd frequency.
• k exceeds len(s): not enough characters. Returns false immediately.
• All characters the same: s = "aaaa", k = 2. odd_count = 0, so 0 is at most 2 is at most 4. Returns true (split into "aa" and "aa").
• Every character unique: s = "abcd", k = 4. odd_count = 4, so 4 is at most 4 is at most 4. Returns true (each character is its own palindrome). But k = 3 would return false because odd_count(4) exceeds k(3).
• Empty string with k equals 0: depending on the problem constraints, this would return true. In practice, the problem guarantees s is non-empty and k is at least 1.

From understanding to recall

You have seen the solution and it makes sense. Count odd frequencies, check two bounds, done. The logic is clean and the code is three lines. But will you remember the exact condition under interview pressure?

The detail that trips people up is the direction of the inequality. Is it odd_count is at most k, or k is at most odd_count? And do you check k against len(s) or against the number of distinct characters? These are small distinctions, but getting them backwards turns a correct solution into a wrong one.

Spaced repetition is how you lock it in. You practice writing the frequency count and the two-bound check from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "partition into k palindromes" and the condition flows out without second-guessing.

Related posts

• Valid Palindrome - The foundational two-pointer palindrome check that teaches the core structure of palindromic strings
• Group Anagrams - Character frequency counting as a grouping key, the same Counter pattern applied to a different problem
• Longest Palindromic Substring - Expand-around-center palindrome detection, a different angle on palindrome structure

CodeBricks breaks the Construct K Palindrome Strings problem into its frequency counting and odd-frequency analysis building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a palindrome feasibility question shows up in your interview, you do not think about it. You just write it.