今日题目

https://leetcode.com/problems/construct-k-palindrome-strings/description/

思路

一个回文串中，最多只能有一个字符的出现次数为奇数。因此，要构造 $k$ 个回文串，字符串 $s$ 中出现次数为奇数的字符最多只能有 $k$ 个。

此外，由于最多只有 26 种不同的字符，若 $26 \leq k$，结果一定为 true。但若 $s$ 的长度小于 $k$，则结果为 false。

下面进行证明。设出现次数为奇数的字符共有 $cntO$ 个，其余所有字符的总出现次数为 $2 \times cntE$。

若所有字符的出现次数均为偶数，只要 $k \leq N$（其中 $N$ 为 $s$ 的总长度），就一定能构造出回文串。这是因为我们可以将一个字符放在回文串最左侧，将其对应的重复字符放在最右侧，从而保持回文结构。

由于 $k \leq N$，可得 $k \leq cntO + 2 \times cntE$，即 $k - cntO \leq 2 \times cntE$。这意味着所有出现次数为奇数的字符可以各自构成一个回文串，共 $cntO$ 个。

我们已经证明：当所有字符出现次数均为偶数时，只要 $k \leq N$，就一定能构造回文串。因此，若 $cntO \le k$，结果为 true，否则为 false。

综上所述，问题最终归结为：当所有字符出现次数均为偶数时，$k \leq N$ 是否成立，而这一条件始终为 true。

技巧

由于最多只有 26 种不同字符，若 $26 \leq k$，结果一定为 true。

解题方法

只需统计每个字符的出现次数，再判断出现次数为奇数的字符数量是否不超过 $k$ 即可。

复杂度分析

  • 时间复杂度：$O(N)$，其中 N 为字符串的长度。

  • 空间复杂度：$O(1)$，仅需存储 26 个字符的计数。

代码

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        cnt = [0] * 26
        if len(s) < k:
            return False
        if k > 25:
            return True
        # The code that makes the code run very fast.
        for ch in s:
            cnt[ord(ch) - ord('a')] += 1
        x = 0
        for i in range(26):
            if cnt[i] % 2 == 1:
                x += 1
        return x <= k

image.png