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^5Hints:
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) —
loading...
Last Post: Sum of Even Fibonacci Numbers
Next Post: What is the largest prime factor of the number 600851475143 ?