MediumNo. 1400

Construct K Palindrome Strings — LeetCode 1400 Python Solution

Pattern
Greedy
Topics
Greedy, Hash Table, String, Counting
Reading time
2 min

The problem

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

Example

Input
s = "annabelle", k = 2
Output
true
Explanation
You can construct two palindromes using all characters in s.

Python solution

PythonSolution
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

Complexity

Time
O(n)
Space · auxiliary
O(C)

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1400. Construct K Palindrome Strings is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems

Frequently asked questions

How hard is LeetCode 1400. Construct K Palindrome Strings?

LeetCode 1400. Construct K Palindrome Strings is rated Medium on LeetCode.

What is the time complexity of LeetCode 1400. Construct K Palindrome Strings?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1400. Construct K Palindrome Strings?

The Python solution on this page uses O(C) auxiliary space.

What topics does LeetCode 1400. Construct K Palindrome Strings cover?

LeetCode 1400. Construct K Palindrome Strings is tagged Greedy, Hash Table, String and Counting on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.