LeetCode 1400. Construct K Palindrome Strings Solution in Java, C++, Python & More | Explanation + Code

Description

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 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 <= 105
• s consists of lowercase English letters.
• 1 <= k <= 105

Solutions

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.

Otherwise, we use a hash table or an array cnt to count the occurrences of each character in string s. Finally, we only need to count the number of characters x that appear an odd number of times in cnt. If x is greater than k, we cannot construct k palindrome strings, so we return false; otherwise, we return true.

The time complexity is O(n), and the space complexity is O(C). Where n is the length of string s, and C is the size of the character set, here C=26.

PythonJavaC++GoTypeScript

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(code-box)

class Solution { public boolean canConstruct(String s, int k) { int n = s.length(); if (n < k) { return false; } int[] cnt = new int[26]; for (int i = 0; i < n; ++i) { ++cnt[s.charAt(i) - 'a']; } int x = 0; for (int v : cnt) { x += v & 1; } return x <= k; } }(code-box)

class Solution { public: bool canConstruct(string s, int k) { if (s.size() < k) { return false; } int cnt[26]{}; for (char& c : s) { ++cnt[c - 'a']; } int x = 0; for (int v : cnt) { x += v & 1; } return x <= k; } };(code-box)

func canConstruct(s string, k int) bool { if len(s) < k { return false } cnt := [26]int{} for _, c := range s { cnt[c-'a']++ } x := 0 for _, v := range cnt { x += v & 1 } return x <= k }(code-box)

function canConstruct(s: string, k: number): boolean { if (s.length < k) { return false; } const cnt: number[] = new Array(26).fill(0); for (const c of s) { ++cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)]; } let x = 0; for (const v of cnt) { x += v & 1; } return x <= k; }(code-box)