LeetCode 1400. 构造 K 个回文字符串
题目描述
题意分析
将字符串的全部字符重新排列并分配成恰好
k个非空回文串，只需判断能否做到，不要求输出具体方案。字符可以任意重排，但每次出现都必须使用，不能舍弃。
解法：字符频次奇偶性判断
核心思路
[!blue]
回文中除中间位置外，字符都能左右配对。设奇数频次的字母种类数为
odd，每种奇频字母总有至少一个无法配对的字符，需要占据某个回文的中心；一个回文至多容纳一个这样的中心，所以必须有odd <= k。每个回文还必须非空，因此也必须有k <= n，其中 $n$ 为字符串长度。这两个条件也足够。若
odd > 0，先将每种奇频字母各取一个作为中心，剩余字符都成对，任意放到这些中心的两侧即可，用完全部字符得到odd个回文。若odd == 0，全部字符成对，直接组成一个非空回文即可。因此最少能先构造出max(1, odd)个回文。如果当前组数还小于 $k\le n$，就必然有一个回文长度至少为 2。长度为 2 时，把它拆成两个单字符回文；长度至少为 3 时，把最外侧相同的一对拿出来组成一个新回文，内部剩余部分仍是非空回文。两种拆分都恰好增加一组，且不丢字符，所以可以逐次达到任意目标 $k$，不需要额外的奇偶限制。
构造过程只用于证明，代码无需真的拆分字符串。先排除
k > n，再统计 26 个小写字母的频次，判断odd <= k即可。
解题步骤
- 长度小于 k 直接失败。
- 统计各字母频次，数出奇数项。
- 判断 odd 不超过 k。
代码实现
class Solution {
public boolean canConstruct(String s, int k) {
// 每个回文必须非空，字符数至少要达到串数。
if (s.length() < k) {
return false;
}
int[] cnt = new int[26];
for (int i = 0; i < s.length(); i++) {
cnt[s.charAt(i) - 'a']++;
}
int odd = 0;
for (int count : cnt) {
if (count % 2 == 1) {
odd++;
}
}
// 奇频字母各需中心，剩余字符对可分配或继续拆分。
return odd <= k;
}
}
func canConstruct(s string, k int) bool {
// 每个回文必须非空，字符数至少要达到串数。
if len(s) < k {
return false
}
cnt := make([]int, 26)
for i := 0; i < len(s); i++ {
cnt[s[i]-'a']++
}
odd := 0
for _, count := range cnt {
if count%2 == 1 {
odd++
}
}
// 奇频字母各需中心，剩余字符对可分配或继续拆分。
return odd <= k
}
复杂度分析
- 时间复杂度：$O(n+26)$。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 数量上限来自非空要求，数量下限来自无法配对的字符。
- k 不必与字符串长度同奇偶。
k = n时每个字符各成一串；k = 1时必须至多只有一种奇频字母。
易错点总结
[!yellow]
- 只判断 odd<=k 会接受字符数量不够的情况。
- 要求 odd==k 会误拒能再拆分的合法方案。
- 只统计不同字母种类，会忽略偶数份字符能够左右配对。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 面试题 01.04. 回文排列 | 简单 | 一个回文最多容纳一种奇数频次，本题构造k个非空回文，需要奇数频次种数不超过k且k不超过串长。 |
| 409. 最长回文串 | 简单 | 原题可舍弃字符求最长回文，本题必须用完全部字符并构成固定数量的非空串。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！