Leetcode 1400. Construct K Palindrome Strings
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!
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.