题目描述
思路解析
一句话答案：LeetCode 1400 构造 K 个回文字符串：用奇字符计数判定，回文最多容一个奇数次字符，故奇数次字符种类数 ≤ k 且串长 ≥ k 便能拼成，时间 O(n)、空间 O(1)。
把字符重排成恰好 k 个回文串，能不能成
给一个只含小写字母的字符串 s 和整数 k，要把 s 的全部字符不多不少地分完、拼成 k 个非空回文串，做得到返回 true，否则 false。回文，就是正着读反着读一样的串。题面例子：s=“annabelle”、k 取 2 返回 true，s=“leetcode”、k 取 3 返回 false。
回文拼法呈爆炸增长，直接数落单字符
先怎么切成 k 段、每段又怎么摆成回文，组合数随长度爆炸增长，枚举验证一长就跑不动。得绕开“怎么拼”，改去数落单字符，只凭字符构成直接拍板。
回文最多一个奇字符，判据就从这来
盯住回文的结构：它左右对称，每个字符都得在中轴两侧成对出现，唯独正中间那个位置能单独站一个落单字符。所以一个回文串里，至多只有一个字符出现奇数次，其余全是偶数次。
推到 k 个回文串上：设 s 里出现奇数次的字符有 oddCount 种，每种都要独占一个回文中心，k 个串顶多提供 k 个中心，于是 oddCount ≤ k。另一头，k 个串都非空、各吃至少一个字符，len 不能比 k 少，即 k ≤ len，若 len ＜ k 就没戏。能构造当且仅当 oddCount ≤ k ≤ len。
三步落地：统计、数奇数、卡两道边界
写成代码只有三步。先扫一遍 s，用频次表数出每个字符出现多少次；再遍历这张表，把出现奇数次的字符种类累加成 oddCount；最后两道边界，先看是否 len ＜ k、是就 false，再看是否 oddCount ≤ k、成立 true 否则 false。参考代码压成一句：len(s) ＜ k 先挡掉，再用 sum(v & 1 for v in cnt.values()) ≤ k 收尾。
两个题面例子从头判一遍
先看 s=“leetcode”、k 取 3。频次：l、t、c、o、d 各 1 次，e 出现 3 次，六种字母共 8 个字符，len=8。数奇数次的种类：1 和 3 都是奇数，竟六种全是奇数次，oddCount=6。代入得 6 ≤ 3 ≤ 8，坏在前半段 6 ≤ 3 不成立——六个奇字符要六中心，三串放不下，返回 false。
再看 s=“annabelle”、k 取 2，长度 9。频次：a、n、e、l 各 2 次全偶数，只有 b 出现 1 次是奇数，oddCount=1。代入 1 ≤ 2 ≤ 9 两头都成立，返回 true，b 落单摆 “elble” 正中。
漏掉上界会错判，等号取不取也藏坑
复杂度上，统计频次扫一遍串是 O(n)，n 是串长；数奇数次字符只在至多 26 个小写字母里转一圈、是常数级，合计 O(n)。频次表最多 26 项、和 n 无关，空间 O(1)。
有两处最容易栽：长度不足直接判假、奇数上界取等。头一处，len ＜ k 时丢了这道上界就要出错：拿 s=“ab”、k 取 3 试，oddCount=2 看着不超过 3，可两个字符凑不出三个非空串，少这道防线就错判成 true。另一处栽在奇数这头取等：判定是 oddCount ≤ k 而非严格小于，取等时每串正好领一个中心、恰好排满。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢一句话:一个回文串最多放一个奇数次字符当中心。于是奇数次字符有几个,就至少要几个回文串;而 k 个非空串又不能比总字符数还多。能构造当且仅当 oddCount ≤ k ≤ len。下面每一帧都在落实这句话。
准备 · 空直方图：开扫之前先看舞台。上面这排是字符串 "leetcode" 的八个字符,右边那张频次表现在还是空的。我们的第一件事,是从左到右扫一遍字符串,把每个字符出现的次数统计进这张表。字符串长度 len 是 8,目标要拼 k 等于 3 个回文串,这两个数先记在心里,后面判定要用。
统计 · 下标 0 读 "l"：扫到下标 0 的字符 "l",它在频次表里还没出现过,于是新加一行,把 l 的次数记成 1。这一步就是在搭这张直方图,字符串里每出现一个新字母,表里就多一行。
统计 · 下标 1 读 "e"：扫到下标 1 的字符 "e",它在频次表里还没出现过,于是新加一行,把 e 的次数记成 1。这一步就是在搭这张直方图,字符串里每出现一个新字母,表里就多一行。
统计 · 下标 2 读 "e"：扫到下标 2 又是 "e",它在表里已经有了,把它的次数从 1 加到 2。你看 "leetcode" 里 e 出现得多,它这一行的数字会一路涨上去,这正是它和别的字母的区别所在。
统计 · 下标 3 读 "t"：扫到下标 3 的字符 "t",它在频次表里还没出现过,于是新加一行,把 t 的次数记成 1。这一步就是在搭这张直方图,字符串里每出现一个新字母,表里就多一行。
统计 · 下标 4 读 "c"：扫到下标 4 的字符 "c",它在频次表里还没出现过,于是新加一行,把 c 的次数记成 1。这一步就是在搭这张直方图,字符串里每出现一个新字母,表里就多一行。
统计 · 下标 5 读 "o"：扫到下标 5 的字符 "o",它在频次表里还没出现过,于是新加一行,把 o 的次数记成 1。这一步就是在搭这张直方图,字符串里每出现一个新字母,表里就多一行。
统计 · 下标 6 读 "d"：扫到下标 6 的字符 "d",它在频次表里还没出现过,于是新加一行,把 d 的次数记成 1。这一步就是在搭这张直方图,字符串里每出现一个新字母,表里就多一行。
统计 · 下标 7 读 "e"：扫到下标 7 又是 "e",它在表里已经有了,把它的次数从 2 加到 3。你看 "leetcode" 里 e 出现得多,它这一行的数字会一路涨上去,这正是它和别的字母的区别所在。
小结 · 直方图建好了：整个字符串扫完,频次表也满了。"leetcode" 一共用到六种字母:l 出现 1 次,e 出现 3 次,t、c、o、d 各出现 1 次。六行加起来正好 8 个字符,跟字符串长度对得上。接下来我们不再关心具体几次,只关心一件事:每个字母的次数,是奇数还是偶数。
洞察 · 回文中心只有一个：在动手判奇偶之前,把最关键的道理想透。一个回文串是左右对称的,任何字符要放进去,都得在对称的两侧各放一个,成对成对地放;只有最中间那一个位置例外,可以单独站一个字符。这就意味着,一个回文串里至多只能有一个字符出现奇数次,就是站中心那个,别的字符必须都是偶数个。所以奇数次的字符有几个,就至少得开几个回文串来安放它们的中心。
判奇偶 · 字母 l：看字母 l,它出现了 1 次。1 是奇数,用位运算说就是 1 和 1 按位与等于 1。它是奇数次,需要一个回文中心来安放,所以把 oddCount 加一,现在累计到 1。
判奇偶 · 字母 e：看字母 e,它出现了 3 次。3 是奇数,用位运算说就是 3 和 1 按位与等于 1。它是奇数次,需要一个回文中心来安放,所以把 oddCount 加一,现在累计到 2。
判奇偶 · 字母 t：看字母 t,它出现了 1 次。1 是奇数,用位运算说就是 1 和 1 按位与等于 1。它是奇数次,需要一个回文中心来安放,所以把 oddCount 加一,现在累计到 3。
判奇偶 · 字母 c：看字母 c,它出现了 1 次。1 是奇数,用位运算说就是 1 和 1 按位与等于 1。它是奇数次,需要一个回文中心来安放,所以把 oddCount 加一,现在累计到 4。
判奇偶 · 字母 o：看字母 o,它出现了 1 次。1 是奇数,用位运算说就是 1 和 1 按位与等于 1。它是奇数次,需要一个回文中心来安放,所以把 oddCount 加一,现在累计到 5。
判奇偶 · 字母 d：看字母 d,它出现了 1 次。1 是奇数,用位运算说就是 1 和 1 按位与等于 1。它是奇数次,需要一个回文中心来安放,所以把 oddCount 加一,现在累计到 6。
小结 · 奇数次字符共 6 个：六个字母挨个判完了,结果有点出人意料:l、t、c、o、d 都只出现 1 次是奇数,而 e 出现 3 次也是奇数,六个字母竟然全是奇数次。所以 oddCount 等于 6。这六个奇数次字符,每一个都得独占一个回文串的中心,也就是说,想安放它们,至少需要 6 个回文串。这个 6 是接下来判定的关键数字。
判定一 · 上界 k ≤ len：先过第一道关:上界。要拼 k 等于 3 个非空回文串,每个串至少要一个字符,所以总字符数 len 必须不小于 k。这里 len 是 8,k 是 3,3 不超过 8,字符数量绰绰有余,上界这关顺利通过。如果反过来 k 比 len 还大,字符根本不够分,那就当场返回 False 了。
判定二 · 下界 oddCount ≤ k：再过第二道关:下界,这道题真正卡住的就是它。我们有 6 个奇数次字符,每个都要一个回文中心,所以最少得开 6 个回文串。可题目只让我们拼 3 个,3 个回文串顶多提供 3 个中心,根本放不下 6 个奇数次字符。oddCount 等于 6,k 等于 3,6 ≤ 3 不成立,这一关过不去。
完成 · 答案 False：把两道关合起来看:能构造的条件是 oddCount ≤ k ≤ len,代进去是 6 ≤ 3 ≤ 8。后半段 3 ≤ 8 没问题,坏在前半段 6 ≤ 3 不成立。说白了,"leetcode" 里奇数次的字符太多,六个中心硬塞不进三个回文串,所以无论怎么拆都拼不出来,答案是 False。
对照 · 能成的例子：换个能拼成的例子体会一下边界。"annabelle" 长度是 9,数一下频次:a 两次、n 两次、e 两次、l 两次都是偶数,只有 b 出现 1 次是奇数,所以 oddCount 等于 1。要拼 k 等于 2 个回文串,代入条件 1 ≤ 2 ≤ 9,三段全成立,答案是 True。那个唯一的奇数次字符 b,放进某个回文串的中心就行,另一个回文串全用偶数次字符,左右对称地凑出来。
边界先想清:每字符各成单字回文是上下界同时取等的临界;奇数次字符比 k 多就 False;字符总数比 k 还少同样 False。
面试重点:回文中心至多一个所以下界是 oddCount、非空串总数不超字符数所以上界是 len、区间内每个 k 都能靠成对字符包壳或拆分的三种放法精确凑出。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def canConstruct(self, s: str, k: int) -> bool: if len(s) < k: return False cnt = Counter(s) return sum(v & 1 for v in cnt.values()) <= k复杂度
- 时间：O(n)，n 是字符串长度。统计每个字符的次数要把整个串扫一遍,是 O(n);之后数奇数次字符,Python 遍历出现过的字符、C 加加 与 Java 遍历固定 26 个桶,都是常数级。合计 O(n)
- 空间：O(1)，只有小写字母,频次容器最多 26 项;C 加加 与 Java 是固定长度 26 的数组,Python 的 Counter 至多 26 个键。这个上限与 n 无关,所以额外空间峰值是常数 O(1)
易错点
面试追问把动画讲成自己的话
追问为什么一个回文串里最多只能有一个字符出现奇数次?
追问为什么判定条件是 oddCount ≤ k ≤ len 这两道边界?
追问只要 k 落在 oddCount 到 len 之间,就一定能构造出来吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
检查一个字符串是否可以打破另一个字符串
LeetCode 1433 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题