构造 K 个回文字符串 图解题解

把字符重排成恰好 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 而非严格小于，取等时每串正好领一个中心、恰好排满。

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()) <= k

C++

#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;
    }
}