原文链接: https://leetcode-cn.com/problems/construct-k-palindrome-strings

英文原文

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

中文题目

给你一个字符串 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^5
• s 中所有字符都是小写英文字母。
• 1 <= k <= 10^5

通过代码

高赞题解

原理

如果一个字符在字符串中出现奇数次，就称这个字符为奇数次出现。
例如字符串”annabelle”，该字符串中字符的出现次数统计如下：

a	b	e	l	n
2	1	2	2	2
只有一种字符’b’奇数次出现。

注意到答案与字符出现的顺序无关，于是不妨将输入的字符串看作字符的集合。

设字符集合s的大小为l，奇数次出现的字符种数为c。
【命题一】若c = 0，则对任意的正整数k <= l，s可以构成k个非空回文串。
【证明】若c = 0，即s中所有字符都是偶数次出现。不妨对s中的字符作替换，使每种字符都出现两次，得到集合s’。
例如s = “aabbbb”，替换为s’ = “aabbcc”。
易见若s’可以构成k个非空回文串，则s也一定可以。

• s’可以构成一个非空回文串，如”abccba”；
• s’可以构成两个……，如”bcacb” + “a”；
• s’可以构成三个……，如”bccb” + “a” + “a”;
• s’可以构成四个……，如”cbc” + “b” + “a” + “a”;
  ……
  ……
• s’可以构成l个……，如”c” + “c” + “b” + “b” + “a” + “a”。

【命题二】s可以构成k个非空回文串当且仅当c <= k <= l.
【证明】
充分性：若c <= k <= l，则用c个奇数次出现的字符（各不相同）可以构成c个回文串。接着只要用剩余的l - c个字符构成k - c个非空回文串即可。注意k - c <= l - c，且剩余的字符中没有奇数次出现了。套用命题一可知这个任务可以完成。
必要性：若k < c，由于每个回文串最多只能含一个奇数次出现，任务无法完成。若l < k，易见任务无法完成。

用命题二就可以编写代码了。

代码

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;
}

统计信息

通过次数	提交次数	AC比率
6058	9970	60.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言