1400. Construct K Palindrome Strings
Description
Given a string s
and an integer k
, 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.
Constraints:
1 <= s.length <= 105
s
consists of lowercase English letters.1 <= k <= 105
Solutions
Solution 1: Counting
First, we check if the length of string $s$ is less than $k$. If it is, we cannot construct $k$ palindrome strings, so we can directly return false
.
Otherwise, we use a hash table or an array $cnt$ to count the occurrences of each character in string $s$. Finally, we only need to count the number of characters $x$ that appear an odd number of times in $cnt$. If $x$ is greater than $k$, we cannot construct $k$ palindrome strings, so we return false
; otherwise, we return true
.
The time complexity is $O(n)$, and the space complexity is $O(C)$. Where $n$ is the length of string $s$, and $C$ is the size of the character set, here $C=26$.
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|