构造 K 个回文字符串 图解题解
这道题到底在问什么
- 输入
- s = "annabelle", k = 2
- 输出
- true(例如 "anna" 加 "elble" 两个回文串)
- 输入
- s = "leetcode", k = 3
- 输出
- false(怎么分都拼不出 3 个回文串)
先想最直接的笨办法
六个字母挨个判完了,结果有点出人意料:l、t、c、o、d 都只出现 1 次是奇数,而 e 出现 3 次也是奇数,六个字母竟然全是奇数次。所以 oddCount 等于 6。这六个奇数次字符,每一个都得独占一个回文串的中心,也就是说,想安放它们,至少需要 6 个回文串。这个 6 是接下来判定的关键数字。（动画第 21 步）
最优解：一步一步想明白
- 3记牢一句话:一个回文串最多放一个奇数次字符当中心。于是奇数次字符有几个,就至少要几个回文串;而 k 个非空串又不能比总字符数还多。能构造当且仅当 oddCount ≤ k ≤ len。下面每一帧都在落实这句话。
- 4开扫之前先看舞台。上面这排是字符串 "leetcode" 的八个字符,右边那张频次表现在还是空的。我们的第一件事,是从左到右扫一遍字符串,把每个字符出现的次数统计进这张表。字符串长度 len 是 8,目标要拼 k 等于 3 个回文串,这两个数先记在心里,后面判定要用。
- 5扫到下标 0 的字符 "l",它在频次表里还没出现过,于是新加一行,把 l 的次数记成 1。这一步就是在搭这张直方图,字符串里每出现一个新字母,表里就多一行。
- 6扫到下标 1 的字符 "e",它在频次表里还没出现过,于是新加一行,把 e 的次数记成 1。这一步就是在搭这张直方图,字符串里每出现一个新字母,表里就多一行。
- 7扫到下标 2 又是 "e",它在表里已经有了,把它的次数从 1 加到 2。你看 "leetcode" 里 e 出现得多,它这一行的数字会一路涨上去,这正是它和别的字母的区别所在。
- 8扫到下标 3 的字符 "t",它在频次表里还没出现过,于是新加一行,把 t 的次数记成 1。这一步就是在搭这张直方图,字符串里每出现一个新字母,表里就多一行。
- 9扫到下标 4 的字符 "c",它在频次表里还没出现过,于是新加一行,把 c 的次数记成 1。这一步就是在搭这张直方图,字符串里每出现一个新字母,表里就多一行。
- 10扫到下标 5 的字符 "o",它在频次表里还没出现过,于是新加一行,把 o 的次数记成 1。这一步就是在搭这张直方图,字符串里每出现一个新字母,表里就多一行。
- 11扫到下标 6 的字符 "d",它在频次表里还没出现过,于是新加一行,把 d 的次数记成 1。这一步就是在搭这张直方图,字符串里每出现一个新字母,表里就多一行。
- 12扫到下标 7 又是 "e",它在表里已经有了,把它的次数从 2 加到 3。你看 "leetcode" 里 e 出现得多,它这一行的数字会一路涨上去,这正是它和别的字母的区别所在。
- 13整个字符串扫完,频次表也满了。"leetcode" 一共用到六种字母:l 出现 1 次,e 出现 3 次,t、c、o、d 各出现 1 次。六行加起来正好 8 个字符,跟字符串长度对得上。接下来我们不再关心具体几次,只关心一件事:每个字母的次数,是奇数还是偶数。
- 14在动手判奇偶之前,把最关键的道理想透。一个回文串是左右对称的,任何字符要放进去,都得在对称的两侧各放一个,成对成对地放;只有最中间那一个位置例外,可以单独站一个字符。这就意味着,一个回文串里至多只能有一个字符出现奇数次,就是站中心那个,别的字符必须都是偶数个。所以奇数次的字符有几个,就至少得开几个回文串来安放它们的中心。
- 15看字母 l,它出现了 1 次。1 是奇数,用位运算说就是 1 和 1 按位与等于 1。它是奇数次,需要一个回文中心来安放,所以把 oddCount 加一,现在累计到 1。
- 16看字母 e,它出现了 3 次。3 是奇数,用位运算说就是 3 和 1 按位与等于 1。它是奇数次,需要一个回文中心来安放,所以把 oddCount 加一,现在累计到 2。
- 17看字母 t,它出现了 1 次。1 是奇数,用位运算说就是 1 和 1 按位与等于 1。它是奇数次,需要一个回文中心来安放,所以把 oddCount 加一,现在累计到 3。
- 18看字母 c,它出现了 1 次。1 是奇数,用位运算说就是 1 和 1 按位与等于 1。它是奇数次,需要一个回文中心来安放,所以把 oddCount 加一,现在累计到 4。
- 19看字母 o,它出现了 1 次。1 是奇数,用位运算说就是 1 和 1 按位与等于 1。它是奇数次,需要一个回文中心来安放,所以把 oddCount 加一,现在累计到 5。
- 20看字母 d,它出现了 1 次。1 是奇数,用位运算说就是 1 和 1 按位与等于 1。它是奇数次,需要一个回文中心来安放,所以把 oddCount 加一,现在累计到 6。
- 21六个字母挨个判完了,结果有点出人意料:l、t、c、o、d 都只出现 1 次是奇数,而 e 出现 3 次也是奇数,六个字母竟然全是奇数次。所以 oddCount 等于 6。这六个奇数次字符,每一个都得独占一个回文串的中心,也就是说,想安放它们,至少需要 6 个回文串。这个 6 是接下来判定的关键数字。
- 22先过第一道关:上界。要拼 k 等于 3 个非空回文串,每个串至少要一个字符,所以总字符数 len 必须不小于 k。这里 len 是 8,k 是 3,3 不超过 8,字符数量绰绰有余,上界这关顺利通过。如果反过来 k 比 len 还大,字符根本不够分,那就当场返回 False 了。
- 23再过第二道关:下界,这道题真正卡住的就是它。我们有 6 个奇数次字符,每个都要一个回文中心,所以最少得开 6 个回文串。可题目只让我们拼 3 个,3 个回文串顶多提供 3 个中心,根本放不下 6 个奇数次字符。oddCount 等于 6,k 等于 3,6 ≤ 3 不成立,这一关过不去。
- 24把两道关合起来看:能构造的条件是 oddCount ≤ k ≤ len,代进去是 6 ≤ 3 ≤ 8。后半段 3 ≤ 8 没问题,坏在前半段 6 ≤ 3 不成立。说白了,"leetcode" 里奇数次的字符太多,六个中心硬塞不进三个回文串,所以无论怎么拆都拼不出来,答案是 False。
- 25换个能拼成的例子体会一下边界。"annabelle" 长度是 9,数一下频次:a 两次、n 两次、e 两次、l 两次都是偶数,只有 b 出现 1 次是奇数,所以 oddCount 等于 1。要拼 k 等于 2 个回文串,代入条件 1 ≤ 2 ≤ 9,三段全成立,答案是 True。那个唯一的奇数次字符 b,放进某个回文串的中心就行,另一个回文串全用偶数次字符,左右对称地凑出来。
⚠️ 容易写错的地方
✗ 错：只判 oddCount ≤ k,忘了上界 k ≤ len
✓ 对：两道边界都要检查,先确认 len ≥ k 再看 oddCount ≤ k
比如 s = "ab"、k = 3,oddCount 是 2 看着 ≤ 3,但字符串只有 2 个字符凑不出 3 个非空串,漏了上界就会错判成 True
✗ 错：以为回文串要求所有字符都成对(全偶)
✓ 对：回文串允许正中间有一个落单的字符,所以每串最多容一个奇数次字符
把条件错记成全偶,就会漏掉中心位置,导致把本来能成的情况判成不能
✗ 错：把判定写成 oddCount 严格小于 k
✓ 对：是 oddCount ≤ k,取等号也成立
oddCount 恰好等于 k 时,正好每个回文串安放一个奇数次字符的中心,刚好排满,依然能构造
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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()) <= kC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
bool canConstruct(string s, int k) {
if (s.size() < k) {
return false;
}
int cnt[26]{};
for (char& c : s) {
++cnt[c - 'a'];
}
int x = 0;
for (int v : cnt) {
x += v & 1;
}
return x <= k;
}
};Java
import java.util.*;
class Solution {
public boolean canConstruct(String s, int k) {
int n = s.length();
if (n < k) {
return false;
}
int[] cnt = new int[26];
for (int i = 0; i < n; ++i) {
++cnt[s.charAt(i) - 'a'];
}
int x = 0;
for (int v : cnt) {
x += v & 1;
}
return x <= k;
}
}复杂度
时间
O(n)
n 是字符串长度。统计每个字符的次数要把整个串扫一遍,是 O(n);之后数奇数次字符,Python 遍历出现过的字符、C 加加 与 Java 遍历固定 26 个桶,都是常数级。合计 O(n)
空间
O(1)
只有小写字母,频次容器最多 26 项;C 加加 与 Java 是固定长度 26 的数组,Python 的 Counter 至多 26 个键。这个上限与 n 无关,所以额外空间峰值是常数 O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 构造 K 个回文字符串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么一个回文串里最多只能有一个字符出现奇数次?+
因为回文串读起来正着反着一样,除了正中间的位置,每个字符都得在对称的两侧各出现一次,成对成对地配。只有当回文串长度是奇数时,正中间会多出一个单独的位置,可以放一个不配对的字符。所以一个回文串里,顶多有一个字符是奇数个,其余全是偶数个。
为什么判定条件是 oddCount ≤ k ≤ len 这两道边界?+
下界来自奇数次字符:有 oddCount 个字符出现奇数次,每个都要独占一个回文中心,所以回文串个数至少 oddCount 个,于是 oddCount ≤ k。上界来自字符总数:k 个回文串每个都非空、至少一个字符,所以字符总数 len 不能少于 k,于是 k ≤ len。两个方向一夹,就得到 oddCount ≤ k ≤ len。
只要 k 落在 oddCount 到 len 之间,就一定能构造出来吗?+
是的,区间里每个 k 都能做到,构造办法是这样:先让每个奇数次字符各自单独成一个回文串,占住自己的中心,用掉 oddCount 个回文串;剩下的字符都是成对的,每一对有三种放法,包到某个已有回文串的最外两侧使个数不变,或单独组成一个长度 2 的回文串使个数加一,或拆成两个长度 1 的回文串使个数加二。每处理一对能让个数加 0、1 或 2,所以从 oddCount 到 len 之间任何一个 k 都能精确凑出来。可见 oddCount ≤ k ≤ len 不只是必要条件,也是充分条件。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 构造 K 个回文字符串 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。