Medium

题目描述

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= s.length <= 10^5
  • s 由小写英文字母组成
  • 1 <= k <= 10^5

解题思路

解题思路

这道题的关键在于理解回文字符串的构造规律。我们需要判断是否能用字符串 s 的所有字符构造出 k 个非空回文字符串。

核心观察：

  1. 回文字符串的特点是对称的，最多只能有一个字符出现奇数次（作为中心字符）
  2. 如果字符串长度小于 k，显然无法构造 k 个非空字符串
  3. 如果出现奇数次的字符超过 k 个，那么我们至少需要那么多个回文字符串来容纳这些"中心字符"

解题步骤：

  1. 首先检查 s.length < k 的情况，直接返回 false
  2. 统计每个字符的出现次数
  3. 计算出现奇数次的字符个数 oddCount
  4. 如果 oddCount > k，返回 false
  5. 否则返回 true

为什么 oddCount ≤ k 就一定可以构造？

  • 每个出现奇数次的字符必须单独占用一个回文字符串的中心位置
  • 剩余的字符都是偶数次，可以平均分配到各个回文字符串中
  • 如果 oddCount < k，我们可以将一些偶数次字符拆分来填充额外的回文字符串

这是一个典型的贪心问题，通过字符计数即可高效解决。

代码实现

class Solution {
public:
    bool canConstruct(string s, int k) {
        if (s.length() < k) return false;
        
        vector<int> count(26, 0);
        for (char c : s) {
            count[c - 'a']++;
        }
        
        int oddCount = 0;
        for (int cnt : count) {
            if (cnt % 2 == 1) {
                oddCount++;
            }
        }
        
        return oddCount <= k;
    }
};

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if len(s) < k:
            return False
        
        from collections import Counter
        count = Counter(s)
        
        odd_count = sum(1 for cnt in count.values() if cnt % 2 == 1)
        
        return odd_count <= k

public class Solution {
    public bool CanConstruct(string s, int k) {
        if (s.Length < k) return false;
        
        int[] count = new int[26];
        foreach (char c in s) {
            count[c - 'a']++;
        }
        
        int oddCount = 0;
        foreach (int cnt in count) {
            if (cnt % 2 == 1) {
                oddCount++;
            }
        }
        
        return oddCount <= k;
    }
}

var canConstruct = function(s, k) {
    if (k > s.length) return false;
    
    const charCount = {};
    for (let char of s) {
        charCount[char] = (charCount[char] || 0) + 1;
    }
    
    let oddCount = 0;
    for (let count of Object.values(charCount)) {
        if (count % 2 === 1) {
            oddCount++;
        }
    }
    
    return oddCount <= k;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历字符串统计字符频次，其中 n 为字符串长度
空间复杂度O(1)只使用固定大小的数组存储26个字母的计数，空间复杂度为常数