1400 - 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 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

Solution 1: Counting

C++

• 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;
      }
  };

JAVA

• 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;
      }
  }

PYTHON

• class Solution:
      def canConstruct(self, s: str, k: int) -> bool:
          if len(s) < k:
              return False
          from collections import Counter
          cnt = Counter(s)
          odd_count = sum(v % 2 for v in cnt.values())
          return odd_count <= k