⚡Flashcard Drill➔
NeetCode #772LC-1400MediumGreedy
← Back to All Problems

#772 · #1400 · Construct K Palindrome Strings(构造 K 个回文字符串)

📌 Problem Statement & Constraints

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. Constraints: 1 <= s.length <= 10^5, 1 <= k <= 10^5, s consists of lowercase English letters.

💡 Core Algorithmic Approaches

  1. A palindrome uses at most one character with an odd count (the centre); every other count must be even.
  2. Let odd be the number of characters whose frequency is odd. Each palindrome can absorb at most one odd character.
  3. So k palindromes are constructible iff odd <= k -- the surplus odd characters can be paired off or absorbed into other palindromes.
  4. Also k cannot exceed the total length, since every palindrome must be non-empty.

💻 Benchmark Python3 Implementation

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if k > len(s):
            return False               # more palindromes than characters
        from collections import Counter
        odd = sum(f % 2 for f in Counter(s).values())
        return odd <= k

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass to count frequencies.
💾 Space Complexity
O(1): at most 26 frequency entries.

⚠️ Interview Pitfalls & Follow-ups

  • Omitting the k > len(s) check: e.g. s = 'a', k = 2 must return false because a palindrome cannot be empty.
  • Requiring odd == k: fewer odd characters than k is fine; the extra palindromes are built from even pairs.
  • Counting characters with even frequency: only odd frequencies matter for the centre argument.
  • Assuming each palindrome must be a single character: they can be arbitrarily long.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems