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
- A palindrome uses at most one character with an odd count (the centre); every other count must be even.
- Let
oddbe the number of characters whose frequency is odd. Each palindrome can absorb at most one odd character. - So
kpalindromes are constructible iffodd <= k-- the surplus odd characters can be paired off or absorbed into other palindromes. - Also
kcannot 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 = 2must return false because a palindrome cannot be empty. - Requiring
odd == k: fewer odd characters thankis 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.