class Solution {
public:
bool canConstruct(string s, int k) {
}
};
1400. 构造 K 个回文字符串
给你一个字符串 s 和一个整数 k 。请你用 s 字符串中 所有字符 构造 k 个非空 回文串 。
如果你可以用 s 中所有字符构造 k 个回文字符串，那么请你返回 True ，否则返回 False 。
示例 1：
输入：s = "annabelle", k = 2 输出：true 解释：可以用 s 中所有字符构造 2 个回文字符串。 一些可行的构造方案包括："anna" + "elble"，"anbna" + "elle"，"anellena" + "b"
示例 2：
输入：s = "leetcode", k = 3 输出：false 解释：无法用 s 中所有字符构造 3 个回文串。
示例 3：
输入：s = "true", k = 4 输出：true 解释：唯一可行的方案是让 s 中每个字符单独构成一个字符串。
示例 4：
输入：s = "yzyzyzyzyzyzyzy", k = 2 输出：true 解释：你只需要将所有的 z 放在一个字符串中，所有的 y 放在另一个字符串中。那么两个字符串都是回文串。
示例 5：
输入：s = "cr", k = 7 输出：false 解释：我们没有足够的字符去构造 7 个回文串。
提示：
1 <= s.length <= 10^5s 中所有字符都是小写英文字母。1 <= k <= 10^5原站题解
c 解法, 执行用时: 12 ms, 内存消耗: 7.5 MB, 提交时间: 2022-12-04 11:39:24
bool canConstruct(char * s, int k){
int table[26] = {0};
int l = strlen(s);
for (int i = 0; i < l; ++i) {
++table[s[i] - 'a'];
}
int count = 0;
for (int i = 0; i < 26; ++i) {
count += table[i] & 1;
}
return count <= k && k <= l;
}
java 解法, 执行用时: 4 ms, 内存消耗: 41.8 MB, 提交时间: 2022-12-04 11:38:04
class Solution {
public boolean canConstruct(String s, int k) {
// 右边界为字符串的长度
int right = s.length();
// 统计每个字符出现的次数
int[] occ = new int[26];
for (int i = 0; i < right; ++i) {
++occ[s.charAt(i) - 'a'];
}
// 左边界为出现奇数次字符的个数
int left = 0;
for (int i = 0; i < 26; ++i) {
if (occ[i] % 2 == 1) {
++left;
}
}
// 注意没有出现奇数次的字符的特殊情况
left = Math.max(left, 1);
return left <= k && k <= right;
}
}
python3 解法, 执行用时: 96 ms, 内存消耗: 15.4 MB, 提交时间: 2022-12-04 11:37:49
class Solution:
def canConstruct(self, s: str, k: int) -> bool:
# 右边界为字符串的长度
right = len(s)
# 统计每个字符出现的次数
occ = collections.Counter(s)
# 左边界为出现奇数次字符的个数
left = sum(1 for _, v in occ.items() if v % 2 == 1)
# 注意没有出现奇数次的字符的特殊情况
left = max(left, 1)
return left <= k <= right