LeetCode 1400. 构造 K 个回文字符串

2024-03-11 HGNULB 约 8 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 1400. 构造 K 个回文字符串

题意分析

给定一个只含小写字母的字符串 s 和整数 k，问能否把 s 中全部字符重新分配到 恰好 $k$ 个非空字符串里，使每个字符串都是回文串。字符不能丢弃也不能新增，顺序可以任意打乱。

「必须用完所有字符」和「恰好 $k$ 个且都非空」这两条一起，先给出一个纯计数的必要条件：$k$ 个非空串至少要吃掉 $k$ 个字符，所以 s.length() < k 时直接不可能。

「可以任意重排」是最强的信号：它意味着字符的位置信息完全无用，能影响答案的只有每个字母出现了多少次，更进一步只有次数的奇偶性。因为回文串的结构约束是「除了正中间可能有一个落单字符，其余字符必须左右成对」，成对与否正是奇偶问题。数据范围 $ s \le 10^5$、$k \le 10^5$ 也印证了答案该是一趟线性扫描，而不是任何形式的枚举划分。

边界有三处：$k = 1$ 时问的是整个 s 能否重排成一个回文串；$k = s $ 时每个串都只能是单字符，而单字符天然是回文，所以必然可行；$k > s $ 时无解。

解法：字符频次奇偶性判断

核心思路

暴力思路是枚举把 $n$ 个字符分成 $k$ 组的所有方案再逐组验回文，方案数是第二类斯特林数量级，$n = 10^5$ 下完全不可行。瓶颈在于「分组方案」这个搜索空间本身就是错误的抽象——题目允许重排，我们根本不关心哪个字符去了哪一组，只关心可行性。

突破口来自回文串的结构刻画：一个长度为 $L$ 的字符串能重排成回文串，当且仅当它内部出现奇数次的字母不超过一个（$L$ 为偶数时必须是 $0$ 个，$L$ 为奇数时恰好 $1$ 个）。把这个条件推广到 $k$ 个串上：设 odd 为 s 中出现奇数次的字母种类数，那么这 odd 个字母各自必须至少有一个「落单」的实例被安置到某个串的正中央，而一个串只提供一个中央位置，所以至少需要 odd 个串，即 k >= odd 是必要条件。

反过来它也是充分的（在 k <= n 的前提下）：先把 odd 个奇数字母各拆出一个单字符串，得到 odd 个合法回文；剩下的全是偶数个的字符，如果还需要再多凑串，就从任意一个剩余字符里拆出一个单字符独立成串（单字符是回文），拆到够 $k$ 个为止——因为 k <= n，字符总量足够支撑这样拆；如果串数已经够了，就把所有剩余字符成对地塞回任意一个已有串的两侧，成对追加不破坏回文性。所以只要 odd <= k <= n，构造一定存在。

于是判定条件就是两个不等式的合取：k <= s.length() 且 odd <= k，其中 odd 是 26 个字母中频次为奇数的个数。注意 odd 与 $n$ 的奇偶性同余，所以这两个不等式不会互相矛盾。

解题步骤

先判 s.length() < k 直接返回 false。这一步必须放最前面：它是与字符内容无关的纯数量约束，提前返回既省掉后续统计，也避免了后面误以为「odd <= k 就够了」。

开一个长度 26 的整型数组 cnt 统计每个小写字母的频次。用定长数组而不是哈希表，是因为字符集固定为 a-z，数组的常数更小且无需装箱；s.charAt(i) - 'a' 把字符映射成 $[0, 25]$ 的下标。

遍历 cnt，把 count % 2 == 1 的种类数累加进 odd。这里只关心奇偶而不关心具体数值，因为偶数份的字符永远可以对称地贴在任意回文串两侧，不消耗「中央位置」这个稀缺资源。

返回 odd <= k。此时 k <= n 已在第一步保证，所以这一个不等式成立就等价于整体可行。

以 s = "annabelle"、k = 2 走一遍：

第一步：s.length() = 9，$9 \ge 2$，不提前返回。
统计频次：a 出现 2 次、n 出现 2 次、b 出现 1 次、e 出现 2 次、l 出现 2 次，其余为 0。
数奇数项：只有 b 的频次 1 是奇数，所以 odd = 1。
判定：$1 \le 2$，返回 true。
验证构造：b 单独成串或放某串中心，剩下 a a n n e e l l 全是偶数份。实际可拆成 "anna" 与 "elble"——前者全偶对称，后者以 b 为中心，恰好 2 个回文串。

再以 s = "leetcode"、k = 3 走一遍：长度 8 不小于 3；频次为 l:1, e:3, t:1, c:1, o:1, d:1，奇数项有 l, e, t, c, o, d 共 6 个，odd = 6；判定 $6 \le 3$ 不成立，返回 false。直观原因是这 6 个落单字符需要 6 个不同的中心，3 个串放不下。

代码实现

class Solution {
    public boolean canConstruct(String s, int k) {
        // k 个非空串至少消耗 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 {
    // k 个非空串至少消耗 k 个字符，这是与内容无关的纯数量约束。
    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 + \Sigma )$，其中 $n = s $、$ \Sigma = 26$。一趟遍历字符串做频次统计，再遍历一次固定长度 26 的计数数组数奇数项，两者都没有嵌套，可直接记作 $O(n)$。

空间复杂度：$O( \Sigma )$ 即 $O(1)$。只额外用了长度恒为 26 的计数数组和两个整型变量，与输入长度无关——这是字符集固定带来的红利，换成 Unicode 才需要哈希表。

关键点总结

题目说「可以重排」时，位置信息立刻作废，问题降级为多重集合上的计数问题；再进一步问「能否两两配对」时，通常只需保留奇偶性而非具体频次。

回文串的可重排刻画要背下来：奇频字母数 $\le 1$。本题是它的多串推广，「一个串一个中心」把资源约束显式化了。

可行性判定题要分别论证必要性与充分性。必要性来自「odd 个中心不可压缩」，充分性来自「偶数份字符可自由对称贴附、单字符必为回文」这条构造。只讲一半在面试里会被追问。

面试视角：面试官通常会先问「为什么只看奇偶就够了」，答「偶数份字符可以对称地贴在任何已有回文的两端，既不改变回文性也不占用中心，所以它们从不构成瓶颈」；接着会问「k <= n 这个条件能不能省」，答不能，s = "a"、k = 2 时 odd = 1 <= 2 但显然造不出两个非空串。

这个「统计奇偶 + 上下界夹逼」的模式可迁移到任何「把多重集拆成若干个满足对称约束的部分」的问题。

易错点总结

漏掉 s.length() < k 的判断：s = "a"、k = 2 时 odd = 1，只看 odd <= k 会返回 true，实际只有一个字符造不出两个非空串。

把条件写成 odd == k：s = "annabelle"、k = 2 时 odd = 1 != 2 会返回 false，而正确答案是 true——多出来的串可以由偶数份字符拆单字符补足。

把条件写成 odd <= k 但忘了 odd 是种类数、误统计成实例数：s = "aaa" 中 a 出现 3 次，若把 3 个 a 都算作奇数实例得到 odd = 3，k = 1 时会错答 false，实际 "aaa" 本身就是回文，答案是 true。

用 count % 2 != 0 处理可能为负的计数：本题频次恒非负所以无碍，但若照搬到含负数的场景，Java 的 % 对负数返回负值，-3 % 2 == -1 不等于 1，判断会漏掉。

数组开成 new int[25]：s 含字母 z 时 'z' - 'a' = 25 越界抛异常。

误以为 k > 26 就无解：s = "aaaa"、k = 4 时只有一种字母，但拆成四个 "a" 完全合法，返回应为 true。

先统计再判长度，且统计时提前 return：逻辑上等价但容易写成先算 odd <= k 就返回，s = "ab"、k = 3 会返回 true（odd = 2 <= 3），正确答案是 false。

用 s.chars().distinct() 之类只数种类不数奇偶：s = "aabb"、k = 1 时种类数为 2 会错答 false，而 "abba" 是回文，正确答案是 true。

把 k 当成上限而非精确值，写成 odd <= k && n >= k 之外还加 n % 2 == k % 2：s = "abc"、k = 2 时 n = 3、k = 2 奇偶不同会被错误否定，实际 "a" 与 "bcb"… 不成立但 "aa" 无从谈起——正确判定是 odd = 3 > 2 返回 false，多加的奇偶条件在别的用例（如 s = "aab"、k = 2）上会误杀。

相似题目

题目	难度	考察点
409. 最长回文串	简单	同样统计奇频字母，但求的是能拼出的最大长度，只允许保留一个中心
面试题 01.04. 回文排列	简单	本题 $k = 1$ 的特例，判据退化为奇频字母数不超过 1
267. 回文排列 II	中等	不止判可行，还要枚举出全部回文排列，需半串全排列去重
1177. 构建回文串检测	中等	多次子串查询，需前缀奇偶异或位掩码把每次查询压到 $O(1)$
242. 有效的字母异位词	简单	同为重排后判等价，但比较的是完整频次向量而非奇偶性
1328. 破坏回文串	中等	反向操作，改一个字符使其不再回文，考的是字典序最小的贪心位置
131. 分割回文串	中等	不允许重排，必须按原顺序切分，退化为回溯搜索加回文预处理
416. 分割等和子集	中等	同为多重集拆分可行性，但约束是子集和相等，需背包 DP 而非计数