贪心题目：构造 K 个回文字符串

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题构造 K 个回文字符串出处1400. 构造 K 个回文字符串难度5 级题目描述要求给定一个字符串s \texttt{s}s和一个整数k \texttt{k}k如果可以用s \texttt{s}s中所有字符构造k \texttt{k}k个回文串则返回true \texttt{true}true否则返回false \texttt{false}false。示例示例 1输入s annabelle, k 2 \texttt{s annabelle, k 2}s annabelle, k 2输出true \texttt{true}true解释可以用s \texttt{s}s中所有字符构造2 \texttt{2}2个回文串。一些可行的构造方案包括anna elble \texttt{anna} \texttt{elble}annaelbleanbna elle \texttt{anbna} \texttt{elle}anbnaelleanellena b \texttt{anellena} \texttt{b}anellenab示例 2输入s leetcode, k 3 \texttt{s leetcode, k 3}s leetcode, k 3输出false \texttt{false}false解释无法用s \texttt{s}s中所有字符构造3 \texttt{3}3个回文串。示例 3输入s true, k 4 \texttt{s true, k 4}s true, k 4输出true \texttt{true}true解释唯一可行的方案是让s \texttt{s}s中每个字符单独构成一个字符串。数据范围1 ≤ s.length ≤ 10 5 \texttt{1} \le \texttt{s.length} \le \texttt{10}^\texttt{5}1≤s.length≤105s \texttt{s}s中所有字符都是小写英语字母1 ≤ k ≤ 10 5 \texttt{1} \le \texttt{k} \le \texttt{10}^\texttt{5}1≤k≤105解法思路和算法为了判断是否可以用字符串s ss中所有字符构造k kk个回文串需要考虑用字符串s ss中所有字符可以构造的回文串个数的最大值和最小值。由于每个回文串的最小长度是1 11因此用字符串s ss中所有字符可以构造的回文串个数的最大值是字符串s ss的长度。回文串的长度可以是奇数或偶数。当回文串的长度是奇数时回文串的中间字符在回文串中的出现次数是奇数回文串中的其余字符在回文串中的出现次数都是偶数。当回文串的长度是偶数时回文串中的所有字符在回文串中的出现次数都是偶数。因此每个回文串中最多有一个字符的出现次数是奇数。用oddCount \textit{oddCount}oddCount表示字符串s ss中的出现次数是奇数的字符个数则用字符串s ss中所有字符可以构造的回文串个数至少为1 11且至少为oddCount \textit{oddCount}oddCount理由如下。由于用字符串s ss中所有字符可以构造的回文串个数是正整数因此至少为1 11。当oddCount 0 \textit{oddCount} 0oddCount0时字符串s ss中的所有字符都出现偶数次对称排列即可得到1 11个回文串。当oddCount 0 \textit{oddCount} 0oddCount0时可以构造oddCount \textit{oddCount}oddCount个回文串每个回文串的中间字符都是在s ss中的出现次数是奇数的字符其余字符的出现次数都是偶数可以对称排列在任意回文串中。当oddCount 0 \textit{oddCount} 0oddCount0时如果用字符串s ss中所有字符构造的字符串个数小于oddCount \textit{oddCount}oddCount则一定存在一个字符串中有至少两个出现奇数次的字符两个出现奇数次的字符无法对称排列因此该字符串不是回文串。因此构造的回文串个数不可能小于oddCount \textit{oddCount}oddCount。当oddCount 0 \textit{oddCount} 0oddCount0时构造oddCount \textit{oddCount}oddCount个回文串之后如果存在回文串的长度大于1 11则可以将长度大于1 11的回文串拆分成多个回文串因此用字符串s ss中所有字符可以构造的回文串个数可以是大于等于oddCount \textit{oddCount}oddCount且小于等于字符串长度的任意正整数。拆分方法如下。回文串的首尾字符一定相同将回文串的首尾字符从回文串分离则剩余的部分仍是回文串分离出的两个字符可以组成一个新回文串。例如原始回文串是“abcba \text{abcba}“abcba将首尾的两个‘a’ \text{a}‘a’分离之后剩余的部分“bcb \text{bcb}“bcb仍是回文串分离出的两个‘a’ \text{a}‘a’可以组成一个新回文串“aa \text{aa}“aa。长度为2 22的回文串可以拆分成两个长度为1 11的回文串。例如回文串“aa \text{aa}“aa可以拆分成两个回文串“a \text{a}“a。根据上述分析可以使用贪心的思想判断是否可以用字符串s ss中所有字符构造k kk个回文串。首先判断k kk与字符串s ss的长度的大小关系如果k kk大于字符串s ss的长度则不能用字符串s ss中所有字符构造k kk个回文串返回false \text{false}false。当k kk小于等于字符串s ss的长度时遍历字符串s ss统计出现次数是奇数的字符个数oddCount \textit{oddCount}oddCount。如果k ≥ oddCount k \ge \textit{oddCount}k≥oddCount则可以用字符串s ss中所有字符构造k kk个回文串返回true \text{true}true否则返回false \text{false}false。代码classSolution{publicbooleancanConstruct(Strings,intk){intlengths.length();if(klength){returnfalse;}int[]countsnewint[26];for(inti0;ilength;i){charcs.charAt(i);counts[c-a];}intoddCount0;for(inti0;i26;i){oddCountcounts[i]%2;}returnkoddCount;}}复杂度分析时间复杂度O ( n ∣ Σ ∣ ) O(n |\Sigma|)O(n∣Σ∣)其中n nn是字符串s ss的长度Σ \SigmaΣ是字符集这道题中Σ \SigmaΣ是全部小写英语字母∣ Σ ∣ 26 |\Sigma| 26∣Σ∣26。当k ≤ n k \le nk≤n时需要遍历字符串一次统计每个字母的出现次数然后遍历每个字母的出现次数计算出现奇数次的字母个数。空间复杂度O ( ∣ Σ ∣ ) O(|\Sigma|)O(∣Σ∣)其中Σ \SigmaΣ是字符集这道题中Σ \SigmaΣ是全部小写英语字母∣ Σ ∣ 26 |\Sigma| 26∣Σ∣26。空间复杂度主要取决于哈希表需要使用哈希表记录每个字母的出现次数。