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

1
2
3
4
5
6
7
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)