#1400

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Construct K Palindrome Strings

Determine if a string's characters can be rearranged to form exactly k non-empty palindrome strings using greedy validation.

hash table string greedy counting

Problem Statement

Given a string s and an integer k, determine whether it is possible to rearrange all characters of s to form exactly k non-empty palindrome strings. Each palindrome must use only the characters from s, and all characters must be used.

Return true if such a construction is possible, and false otherwise. For example, s = "annabelle" with k = 2 returns true because you can form palindromes like "anna" + "elble". Conversely, s = "leetcode" with k = 3 returns false because there are too many odd-count characters to distribute among 3 palindromes.

Examples

Example 1

Input: s = "annabelle", k = 2

Output: true

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

It is impossible to construct 3 palindromes using all the characters of s.

Example 3

Input: s = "true", k = 4

Output: true

The only possible solution is to put each character in a separate string.

Constraints

1 <= s.length <= 105
s consists of lowercase English letters.
1 <= k <= 105

Solution Approach

Validate String Length

Immediately return false if the length of s is less than k, since you cannot form more palindromes than available characters. This is the first greedy choice and prevents unnecessary computation.

Count Character Frequencies

Use a hash table to count each character's occurrences. Track how many characters have odd frequencies, since each palindrome can contain at most one odd-count character. This counting ensures we respect the invariant that the number of palindromes must be at least the number of odd characters.

Check Odd Count Constraint

Return true if the number of characters with odd counts is less than or equal to k. This guarantees a feasible arrangement into k palindromes, applying the greedy pattern: assign odd-count characters first, then fill with even-count characters to complete each palindrome.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because each character is counted once. Space complexity is O(1) since the hash table only stores up to 26 lowercase letters, independent of string length.

What Interviewers Usually Probe

They may ask how to handle s.length < k efficiently.
They might probe the logic behind counting odd-frequency characters.
They could ask why a greedy allocation ensures correctness in forming k palindromes.

Common Pitfalls or Variants

Common pitfalls

Forgetting to return false when s.length < k, which immediately invalidates the construction.
Miscounting odd-frequency characters or assuming even counts are irrelevant.
Attempting to construct palindromes explicitly rather than reasoning with counts, wasting time and space.

Follow-up variants

Construct k palindrome strings with additional constraints, like each palindrome having equal length.
Determine the maximum k for which a given s can form exactly k palindromes.
Check if s can form k palindromes where each contains at least one specific character.

FAQ

What is the first check to do for Construct K Palindrome Strings?

Always check if s.length < k first, because you cannot create k non-empty palindromes with fewer characters than k.

Why do we count characters with odd frequencies?

Each palindrome can have at most one character with an odd count, so the number of odd-count characters determines the minimum required palindromes.

Can I form k palindromes if the number of odd characters exceeds k?

No, it's impossible because each odd-count character must occupy its own palindrome, violating the k limit.

Does GhostInterview build the palindromes explicitly?

No, it focuses on validating counts and greedy allocation, showing feasibility without constructing each string.

What pattern does this problem exemplify?

It uses a greedy choice plus invariant validation pattern, ensuring the number of odd-count characters fits within k palindromes.

terminal

Solution

Solution 1: Counting

First, we check if the length of string $s$ is less than $k$. If it is, we cannot construct $k$ palindrome strings, so we can directly return `false`.

1

2

3

4

5

6

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if len(s) < k:
            return False
        cnt = Counter(s)
        return sum(v & 1 for v in cnt.values()) <= k

Continue Practicing

#767 reorganize string #2131 longest palindrome by concatenating two letter words #2182 construct string with repeat limit