构造 K 个回文字符串

难度: 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
解释：唯一可行的方案是让 s 中每个字符单独构成一个字符串。

示例 4：

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

示例 5：

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

提示：

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

Submission

运行时间: 60 ms

内存: 17.1 MB

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        if k> len(s):
            return False
        counter=Counter(s)
        ans=0
        for i in counter.values():
            if i%2:
                ans+=1
        return ans<=k

Explain

要构造k个回文字符串，首先考虑基本的回文特性：一个回文字符串中，除了最多一个字符可以出现奇数次，其余所有字符都应该出现偶数次。针对这个属性，我们可以首先统计字符串s中每个字符的出现次数。如果s的长度小于k，显然无法构造k个非空回文字符串，直接返回False。接着，统计有多少个字符的出现次数是奇数（这些奇数次数的字符分别至少需要一个回文字符串来容纳它们自己）。如果奇数次数的字符数大于k，那么也不能构成k个回文字符串。否则，可以通过调整字符的分配来满足构造k个回文字符串的要求。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        # 如果要构造的回文字符串数k大于s的长度，则不可能构造k个非空回文字符串
        if k > len(s):
            return False
        
        # 统计每个字符出现的次数
        counter = Counter(s)
        
        # 统计有多少个字符出现了奇数次
        odd_count = 0
        for count in counter.values():
            if count % 2 == 1:
                odd_count += 1
        
        # 如果奇数次数的字符数不超过k，则可以构造k个回文字符串
        return odd_count <= k

Explore

回文字符串的特性是，除了最多一个字符可以出现奇数次，其余所有字符都应该出现偶数次。因此，如果有多个字符出现了奇数次，每个这样的字符至少需要一个单独的回文字符串来放置这个奇数次的字符，以确保其他字符都能成对出现。如果奇数次的字符数量超过了可用的回文字符串数量k，那么将没有足够的回文字符串来分别容纳这些奇数次字符，从而无法形成k个回文字符串。

Python的Counter类是基于字典的，它可以统计任何可哈希的对象的出现次数，包括所有的Unicode字符。因此，使用Counter类来统计字符串中字符的出现次数是适用于包括非英文字母在内的所有字符集的。这使得Counter类非常适合处理多语言文本或包含各种符号和表情的字符串。

如果字符串s的长度小于k，意味着至少有k个位置需要被填充以形成k个非空回文字符串。每个回文字符串至少需要一个字符，所以当s的长度小于k时，就不可能构造出k个非空的回文字符串，因为没有足够的字符来填充每个回文字符串至少一个字符。这是一个简单的数学上的限制。

题解中使用的遍历Counter值的方法是一个直观且有效的方式来统计奇数次字符的数量。尽管这种方法涉及遍历所有字符的计数，但在大多数情况下，这是效率相对较高的，因为字符种类通常远少于字符串的长度。然而，也可以在统计字符的同时维护一个奇数次数计数器，每次字符出现时，更新其计数，并相应地调整奇数次数计数器（如果字符计数从偶数变为奇数，增加奇数次计数器，从奇数变为偶数，则减少奇数次计数器）。这可能在某些情况下提高效率，尤其是在极长的字符串中。