1400. Construct K Palindrome Strings LeetCode Solution

Last updated: February 23, 2025

In this guide, you will get 1400. Construct K Palindrome Strings LeetCode Solution with the best time and space complexity. The solution to Construct K Palindrome Strings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Construct K Palindrome Strings solution in C++
Construct K Palindrome Strings solution in Java
Construct K Palindrome Strings solution in Python
Additional Resources

1400. Construct K Palindrome Strings LeetCode Solution image

Problem Statement of Construct K Palindrome Strings

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

1400. Construct K Palindrome Strings LeetCode Solution in C++

class Solution {
 public:
  bool canConstruct(string s, int k) {
    // If |s| < k, we cannot construct k strings from the s.
    if (s.length() < k)
      return false;

    bitset<26> odd;

    for (const char c : s)
      odd.flip(c - 'a');

    // If the number of letters that have odd counts > k, the minimum number of
    // palindromic strings we can construct is > k.
    return odd.contains() <= k;
  }
};
/* code provided by PROGIEZ */

1400. Construct K Palindrome Strings LeetCode Solution in Java

class Solution {
  public boolean canConstruct(String s, int k) {
    // If |s| < k, we cannot construct k strings from the s.
    if (s.length() < k)
      return false;

    int[] count = new int[26];

    for (final char c : s.toCharArray())
      count[c - 'a'] ^= 1;

    // If the number of letters that have odd counts > k, the minimum number of
    // palindromic strings we can construct is > k.
    return Arrays.stream(count).filter(c -> c % 2 == 1).count() <= k;
  }
}
// code provided by PROGIEZ

1400. Construct K Palindrome Strings LeetCode Solution in Python

class Solution:
  def canConstruct(self, s: str, k: int) -> bool:
    # If |s| < k, we cannot construct k strings from the s.
    # If the number of letters that have odd counts > k, the minimum number of
    # palindromic strings we can construct is > k.
    return sum(freq & 1
               for freq in collections.Counter(s).values()) <= k <= len(s)
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents