题目大意：
构造 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 个回文串。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1400
解题思路分析：
回文是由多个两两一组的相同字符组成，另外回文的中间可以是一个单独的字符，也就是说一个回文可以包含多组相同的字符以及一个单独的字符。解题时，我们遍历一遍字符串中的每一个字符，统计出两两一组的相同字符的组数，以及单独字符的个数，比如aaaaa，我们可以认为它拥有2组相同字符（2个aa）以及1个单独字母a，再比如aaabbc，他有2组相同字符aa和bb，并且剩下2个单独字符a和c。
统计后，如果单独字符的个数大于k，这肯定是不行的，因为每个回文最多只能容纳一个单独字符，返回false。另外如果单独字符个数加上相同字符的组数大于等于k，那么我们可以轻松并随意的将它们放置到k个回文中，此时返回true。
最后一种情况，如果单独字符个数加上相同字符的组数小于k，也就是说我们用每一对字符与每一个单独字符分别组成一个回文仍然不够k个回文的情况，比如aac，我们有一组aa和一个单独字符c，当k是3时，显然aa和c两个回文的个数不足3，不过这时不要急于返回false，因为我们可以将aa差分为两个a，这样就可以满足题意。所以当遇到这种情况时，我们可以不断循环的将一个字符组差分成2个单独字符，直到满足两者的个数相加大于等于k为止。不过在循环中当字符组的个数小于0，或者单独字符个数大于k时，需要返回false。
实现代码：
public boolean canConstruct(String s, int k) {
int doubleCount=0;
int singleCount=0;
int[] count = new int[26];
char[] arr=s.toCharArray();
for(int i=0;i<s.length();i++){
count[arr[i]-'a']++;
if(count[arr[i]-'a']==1){
singleCount++;
}else{
singleCount--;
doubleCount++;
count[arr[i]-'a']=0;
}
}
if(singleCount>k) return false;
while(doubleCount>=0&&singleCount<=k){
if(doubleCount+singleCount>=k) return true;
doubleCount--;
singleCount+=2;
}
return false;
}本题解法执行时间为12ms。
Runtime: 12 ms, faster than 37.94% of Java online submissions for Construct K Palindrome Strings.
Memory Usage: 39.7 MB, less than 100.00% of Java online submissions for Construct K Palindrome Strings.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1400-construct-k-palindrome-strings-解题思路分析/