Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1400.html
1400. Construct K Palindrome Strings (Medium)
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^5
Related Topics:
Greedy
Solution 1.
Trivial cases:
k > N
,false
k == N
,true
Then just count the characters with odd frequency. Return true
is the frequency <= k
.
// OJ: https://leetcode.com/problems/construct-k-palindrome-strings/
// Time: O(N)
// Space: O(1)
class Solution {
public:
bool canConstruct(string s, int k) {
int N = s.size();
if (k > N) return false;
if (k == N) return true;
int cnt[26] = {0};
for (char c : s) cnt[c - 'a']++;
int sum = 0;
for (int i = 0; i < 26; ++i) if (cnt[i] % 2) ++sum;
return sum <= k;
}
};
-
class Solution { public boolean canConstruct(String s, int k) { int length = s.length(); if (length < k) return false; if (length == k) return true; int[] counts = new int[26]; for (int i = 0; i < length; i++) { char c = s.charAt(i); counts[c - 'a']++; } int oddCount = 0; for (int i = 0; i < 26; i++) { if (counts[i] % 2 == 1) oddCount++; } return oddCount <= k; } } ############ class Solution { public boolean canConstruct(String s, int k) { if (s.length() < k) { return false; } int[] counter = new int[26]; for (char c : s.toCharArray()) { ++counter[c - 'a']; } int cnt = 0; for (int v : counter) { if (v % 2 == 1) { ++cnt; } } return cnt <= k; } }
-
// OJ: https://leetcode.com/problems/construct-k-palindrome-strings/ // Time: O(N) // Space: O(1) class Solution { public: bool canConstruct(string s, int k) { int N = s.size(); if (k > N) return false; if (k == N) return true; int cnt[26] = {0}; for (char c : s) cnt[c - 'a']++; int sum = 0; for (int i = 0; i < 26; ++i) if (cnt[i] % 2) ++sum; return sum <= k; } };
-
class Solution: def canConstruct(self, s: str, k: int) -> bool: if len(s) < k: return False counter = Counter(s) cnt = sum(1 for n in counter.values() if n % 2 == 1) return cnt <= k
-
func canConstruct(s string, k int) bool { if len(s) < k { return false } counter := make([]int, 26) for _, c := range s { counter[c-'a']++ } cnt := 0 for _, v := range counter { if v%2 == 1 { cnt++ } } return cnt <= k }
-
function canConstruct(s: string, k: number): boolean { if (s.length < k) { return false; } const cnt: number[] = new Array(26).fill(0); for (const c of s) { ++cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)]; } let x = 0; for (const v of cnt) { x += v & 1; } return x <= k; }