专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
最近一网友发文称：在字节一面二面三面都很顺利，面试官还夸他优秀，结果三面的时候直接把他给挂了。另一网友评论说他们组会把面试者照片发到群里让大家选哪个最好看选择哪个。我听过卡学历，卡年龄，甚至卡性别的，但卡颜值的还是第一次听过。
如果是面向大众的工作，比如车模，销售，服务员，卡颜值还能理解，毕竟他们面向的是客户，颜值高的确有优势。如果是对着电脑工作，卡颜值就没必要了。不过一般来说一份工作不会只找一个人来面试，如果所有面试者都很优秀，学历，年龄都难分伯仲，卡颜值也未尝不可。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第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 中每个字符单独构成一个字符串。
1 <= s.length <= 10^5
s 中所有字符都是小写英文字母。
1 <= k <= 10^5
问题分析
这题说的是使用字符串中的所有字符构造 k 个回文串，如果字符串的长度小于 k ，无论如何也是完成不了的。如果字符串的长度不小于 k ，我们需要统计字符串中每个字符出现的次数。
如果每个字符出现的次数都是偶数，我们可以构造成任意 1<=k<=n 个回文子串，比如字符串aabbcccc，可构造的回文子串如下：
[abccccba]
[abba,cccc]
[aa,bb,cccc]
[aa,bb,cc,cc]
[aa,bb,cc,c,c]
[aa,bb,c,c,c,c]
[aa,b,b,c,c,c,c]
[a,a,b,b,c,c,c,c]
如果某个字符出现的个数是奇数，要想构造最少的回文串，该字符串必须要在回文串的中间，比如aaabbcc要构成一个回文串，则aaa必须要放到中间，如果有构成两个回文串则不需要放到中间。
再来看一个示例，比如字符串aaabbbcc，如果要构成一个回文串，无论如何也是实现不了的，因为字符 a 和字符 b 出现的次数都是奇数，但要构成两个回文串是可以的。
所以我们可以得出如果字符串中出现奇数次的字符个数大于 k 的时候，我们是无法分割成 k 个回文串的，否则是可以的。我们只需要统计出现奇数次字符的个数即可。
JAVA：
public boolean canConstruct(String s, int k) { if (k > s.length()) return false; int[] mp = new int[128]; for (char ch : s.toCharArray()) mp[ch]++; int odd = 0;// 奇数的个数 for (int cnt : mp) { if (cnt % 2 == 1) odd++; } return k >= odd; }C++：
public: bool canConstruct(string s, int k) { if (k > s.length()) returnfalse; vector
mp(128, 0); for (constauto &ch: s) mp[ch]++; int odd = 0;// 奇数的个数 for (constauto cnt: mp) { if (cnt % 2 == 1) odd++; } return k >= odd; }
笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴