Construct K Palindrome Strings

You may rearrange the characters of s and divide them into exactly k nonempty strings, using every character exactly once. Return true if all k strings can be palindromes, and false otherwise. A palindrome reads the same from left to right and from right to left.

Example 1:

Input: s = "aabbc"
k = 2

Output: true

Explanation: Rearrange the characters into "abba" and "c". Both strings are nonempty palindromes, and together they use every character exactly once.

Example 2:

Input: s = "abc"
k = 2

Output: false

Explanation: Each of a, b, and c occurs once. A palindrome can have at most one unpaired letter, so these characters require three palindromes rather than two.

Example 3:

Input: s = "aa"
k = 3

Output: false

Explanation: Two characters cannot fill three nonempty strings, so the requested construction is impossible.

Constraints:

• 1 <= s.length <= 100000
• s contains only lowercase English letters.
• 1 <= k <= 100000