Skip to content

1400. Construct K Palindrome Strings 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  bool canConstruct(string s, int k) {
    // If the s.length() < k, we cannot construct k strings from s.
    if (s.length() < k)
      return false;

    bitset<26> odd;

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

    // If the # of characters that have odd counts is > k, the min # of
    // palindrome strings we can construct is > k.
    return odd.count() <= k;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public boolean canConstruct(String s, int k) {
    // If the s.length() < k, we cannot finalruct k strings from s.
    if (s.length() < k)
      return false;

    int[] count = new int[26];

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

    // If the # of characters that have odd counts is > k, the min # of
    // palindrome strings we can finalruct is > k.
    return Arrays.stream(count).filter(c -> c % 2 == 1).count() <= k;
  }
}

1
2
3
4
5
6
class Solution:
  def canConstruct(self, s: str, k: int) -> bool:
    # If the len(s) < k, we cannot construct k strings from s.
    # If the # of characters that have odd counts is > k, the min # of
    # palindrome strings we can construct is > k.
    return sum(freq & 1 for freq in collections.Counter(s).values()) <= k <= len(s)