题目描述

给你一个字符串 s 和一个整数 k。请你用 s 字符串中 所有字符 构造 k 个非空 回文串。

如果你可以用 s 中所有字符构造 k 个回文字符串，那么请你返回 True，否则返回 False。

样例

输入：s = "annabelle", k = 2
输出：true
解释：可以用 s 中所有字符构造 2 个回文字符串。
一些可行的构造方案包括："anna" + "elble"，"anbna" + "elle"，"anellena" + "b"

输入：s = "leetcode", k = 3
输出：false
解释：无法用 s 中所有字符构造 3 个回文串。

输入：s = "true", k = 4
输出：true
解释：唯一可行的方案是让 s 中每个字符单独构成一个字符串。

输入：s = "yzyzyzyzyzyzyzy", k = 2
输出：true
解释：你只需要将所有的 z 放在一个字符串中，所有的 y 放在另一个字符串中。
那么两个字符串都是回文串。

输入：s = "cr", k = 7
输出：false
解释：我们没有足够的字符去构造 7 个回文串。

限制

• 1 <= s.length <= 10^5
• s 中所有字符都是小写英文字母。
• 1 <= k <= 10^5

算法

(找规律) $O(n)$

1. 如果字符串长度小于 k，则直接返回 false。
2. 统计每个字母的出现次数。
3. 我们发现，如果某个字母出现了奇数次，则这个字母必须作为某一个奇回文串的中心字母。
4. 这样，我们可以统计出现次数为奇数的字符的数量，如果这个数量小于等于 k，则说明可以完成构造。

时间复杂度

• 遍历字符串一次，时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool canConstruct(string s, int k) {
        if (k > s.length())
            return false;

        vector<int> cnt(26, 0);
        for (char c : s)
            cnt[c - 'a']++;

        int odd = 0;
        for (int i = 0; i < 26; i++)
            if (cnt[i] & 1)
                odd++;

        return odd <= k;
    }
};