Is Construct K Palindrome Strings easy or hard?

Construct K Palindrome Strings is considered a Medium problem on LeetCode. The main challenge is recognizing the palindrome property related to odd character counts. Once that insight is clear, the implementation becomes straightforward and efficient.

Construct K Palindrome Strings Python/Java solution

In Python or Java, the implementation counts character frequencies and checks the number of odd counts. Python often uses collections.Counter, while Java typically uses an int[26] array. Both implementations run in O(n) time and O(1) extra space.

How to solve Construct K Palindrome Strings in O(n)?

Count the frequency of each character in the string. Compute how many characters appear an odd number of times. If the odd count is greater than k, forming k palindromes is impossible; if the string length is less than k, it is also impossible. Otherwise, you can distribute character pairs across palindromes and return true.

What is the best approach for Construct K Palindrome Strings?

The best approach is character frequency counting with a greedy check. Count how many characters have odd frequencies and ensure that number is less than or equal to k, since each palindrome can contain only one odd center. Also verify that the string length is at least k. This runs in O(n) time with O(1) space.

Is Construct K Palindrome Strings asked at Google/Amazon/Meta?

Palindrome construction and frequency counting problems are common in interviews at companies like Amazon, Google, and Meta. Variations of this problem test understanding of string manipulation, greedy reasoning, and counting techniques using hash maps or arrays.

What data structure is used in Construct K Palindrome Strings?

The typical solution uses a frequency array or hash table to count occurrences of each character. Since the problem usually involves lowercase English letters, a fixed array of size 26 is sufficient and provides constant-space performance.

What is the time complexity of Construct K Palindrome Strings?

The optimal solution runs in O(n) time where n is the length of the string. You perform a single pass to count character frequencies and another pass over the frequency array to count odd occurrences. Space complexity is O(1) because the alphabet size is fixed (26 lowercase letters).

Description Hints 3 Solution Video 5:30

1400. Construct K Palindrome Strings

Medium68.6% acceptance6 companies

Given a string s and an integer k, return true if you can use all the characters in s to construct k palindrome strings or false otherwise.

Example 1:

Input: s = "annabelle", k = 2
Output: true
Explanation: 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
Explanation: It is impossible to construct 3 palindromes using all the characters of s.

Example 3:

Input: s = "true", k = 4
Output: true
Explanation: The only possible solution is to put each character in a separate string.

Constraints:

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

Asked at 6 companies

Uber

Google Amazon Microsoft Meta Bloomberg

Topics

Hints open one at a time

Hint 1

If the s.length < k we cannot construct k strings from s and answer is false.

Hint 2

If the number of characters that have odd counts is > k then the minimum number of palindrome strings we can construct is > k and answer is false.

Hint 3

Otherwise you can construct exactly k palindrome strings and answer is true (why ?).

5:30

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def canConstruct(self, s: str, k: int) -> bool:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"annabelle"
2

Input

"leetcode"
3

Input

"true"
4

Your code is saved on this device.Solution