题目描述
思路解析动画文字版
记牢一句话:一个回文串最多放一个奇数次字符当中心。于是奇数次字符有几个,就至少要几个回文串;而 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题