Given a string s and an integer k. You should construct k non-empty palindrome strings using all the characters in s. 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.

Example 4:
Input: s = “yzyzyzyzyzyzyzy”, k = 2
Output: true
Explanation: Simply you can put all z’s in one string and all y’s in the other string. Both strings will be palindrome.

Example 5:
Input: s = “cr”, k = 7
Output: false
Explanation: We don’t have enough characters in s to construct 7 palindromes.

Constraints:
1 <= s.length <= 10^5
All characters in s are lower-case English letters.
1 <= k <= 10^5

Hints:
If the s.length < k we cannot construct k strings from s and answer is false.
If the number of characters that have odd counts is bigger than k then the minimum number of palindrome strings we can construct is > k and answer is false.
Otherwise you can construct exactly k palindrome strings and answer is true (why ?).

Algorithm to Construct K Palindrome Strings

We can count the frequency of the characters in the input set. If we have M characters which are of odd frequencies, we can construct at least M-1 palindromes.

If the given input character set is larger than K, we definitely can’t form K palindromes. We can count the frequencies of characters using a static array since the letters are lowercase.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    bool canConstruct(string s, int k) {
        if (s.size() < k) return false;
        int count[26] = {};
        for (const auto &n: s) count[n - 97] ++;
        int odd = 0;
        for (int i = 0; i < 26; ++ i) {
            if (count[i] & 1) {
                odd ++;
            }
        }
        return odd <= k;
    }
};

class Solution {
public:
    bool canConstruct(string s, int k) {
        if (s.size() < k) return false;
        int count[26] = {};
        for (const auto &n: s) count[n - 97] ++;
        int odd = 0;
        for (int i = 0; i < 26; ++ i) {
            if (count[i] & 1) {
                odd ++;
            }
        }
        return odd <= k;
    }
};

Alternatively, we can use the std::bitset to flip and count.

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    bool canConstruct(string s, int k) {
        if (s.size() < k) return false;
        bitset<26> odd;
        for (const auto &n: s) {
            odd.flip(n - 97);
        }
        return odd.count() <= k;
    }
};

class Solution {
public:
    bool canConstruct(string s, int k) {
        if (s.size() < k) return false;
        bitset<26> odd;
        for (const auto &n: s) {
            odd.flip(n - 97);
        }
        return odd.count() <= k;
    }
};

Both implementation run at O(N) time and O(1) constant space, where N is the length of the string s.

–EOF (The Ultimate Computing & Technology Blog) —