Problem Statement

Given a string and an integer, the goal is to determine if it is possible to construct the specified number of palindrome strings using all the current characters in the string.

More formally, given a string s and an integer k, you are required to construct k non-empty palindrome strings using all characters in s. If all the characters from s can be used to construct k palindrome strings, we return True, otherwise, we return False.

Examples

Example 1: Input: s = "annabelle", k = 2 Output: true Explanation: We can get two palindromes from s like "anna" + "elble", "anbna" + "elle", "anellena" + "b", where each palindrome uses the characters in s.

Example 2: Input: s = "leetcode", k = 3 Output: false Explanation: It is not possible to construct 3 palindromes using all the characters of s.

Example 3: Input: s = "true", k = 4 Output: true Explanation: We can separate each character to make a palindrome, hence "t","r","u","e" are the possible palindromes.

Constraints

• 1 <= s.length <= 10^5
• All characters in s are lowercase English letters.
• 1 <= k <= 10^5

Approach

Our target is to create k palindromes. If the length of s is less than k, then it's impossible to create k palindromes because we cannot form a palindrome with no characters, so we return False. Thus we can say s.length() >= k is the minimum requirement to form k palindromes.

Now let's say s has x characters whose counts are odd then we can form minimum x palindrome strings using s. If x > k we can't form k palindromes as the minimum number of palindromes we can from s is x > k so we return False. And if x <= k then when length of s is greater than or equal to k, we can always form k palindromes.

To count the number of characters in s which appear an odd number of times, we can use a bitset implementation. For each character in s, we flip the corresponding bit in our bitset. Finally, the count of our bitset represents the number of characters in s that appear an odd number of times.

Python Solution

1
2python
3class Solution:
4    def canConstruct(self, s: str, k: int) -> bool:
5        if len(s) < k:
6            return False
7        odd = [0]*26
8        for c in s:
9            # flip the bit for each character
10            odd[ord(c) - ord('a')] ^= 1
11        count = sum(odd)
12        # if count is less or equal to k, we can form k palindromes
13        return count <= k

Java Solution

1
2java
3public class Solution {
4    public boolean canConstruct(String s, int k) {
5        if (s.length() < k)
6            return false;
7
8        int[] odd = new int[26];
9
10        for (char c : s.toCharArray())
11            odd[c - 'a'] ^= 1;
12        
13        int count = 0;
14        for (int i : odd)
15            if (i != 0) count++;
16
17        return count <= k;
18    }
19}

Javascript Solution

1
2javascript
3class Solution {
4    canConstruct(s, k) {
5        if (s.length < k)
6            return false;
7
8        let odd = new Array(26).fill(0);
9
10        for (let c of s)
11            odd[c.charCodeAt(0) - 'a'.charCodeAt(0)] ^= 1;
12        
13        let count = 0;
14        for (let i of odd)
15            if (i != 0) count++;
16
17        return count <= k;
18    }
19}

C++ Solution

1
2c++
3class Solution {
4public:
5    bool canConstruct(string s, int k) {
6        if (s.length() < k)
7            return false;
8
9        vector<int> odd(26, 0);
10
11        for (char c : s)
12            odd[c - 'a'] ^= 1;
13        
14        int count = 0;
15        for (int i : odd)
16            if (i != 0) count++;
17        
18        return count <= k;
19    }
20};

C# Solution

1
2csharp
3public class Solution {
4    public bool CanConstruct(string s, int k) {
5        if (s.Length < k)
6            return false;
7
8        int[] odd = new int[26];
9
10        foreach (char c in s)
11            odd[c - 'a'] ^= 1;
12        
13        int count = 0;
14        foreach (int i in odd)
15            if (i != 0) count++;
16
17        return count <= k;
18    }
19}

Ruby Solution

1
2ruby
3class Solution 
4    def can_construct(s, k) 
5        return false if s.length < k 
6
7        odd = Array.new(26, 0)
8
9        s.each_char { |c| odd[c.ord - 'a'.ord] ^= 1 }
10
11        count = odd.count{ |i| i != 0 }
12
13        return count <= k 
14    end 
15end

Swift Solution

1
2swift
3class Solution {
4    func canConstruct(_ s: String, _ k: Int) -> Bool {
5        guard s.count >= k else {
6            return false
7        }
8
9        var odd = Array(repeating: 0, count: 26)
10
11        for c in s.utf8 {
12            odd[Int(c) - 97] ^= 1
13        }
14
15        let count = odd.filter { $0 != 0 }.count
16
17        return count <= k
18    }
19}

Conclusion

In this problem, we learned how to use binary operations to count the occurrence of characters in a string. This is a useful skill in handling string-related problems. Understanding this problem not only helps improve our problem-solving skills but also helps in gaining a good grasp of bit manipulations, which play a crucial role in competitive programming. This technique of counting letters can be applied to various other problems such as Anagrams, Palindromes, etc.

In the future, by applying such methods and techniques, we should be able to solve more complex and challenging string-related problems. Happy coding!