1400. 构造 K 个回文字符串 #

标签：贪心、哈希表、字符串、计数
难度：中等

题目大意 #

描述：给定一个字符串 s 和一个整数 k。

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

说明：

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

示例：

示例 1：

1
2
3
4


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

解题思路 #

思路 1：贪心算法 #

用字符串 s 中所有字符构造回文串最多可以构造 len(s) 个（将每个字符当做一个回文串）。所以如果 len(s) < k，则说明字符数量不够，无法构成 k 个回文串，直接返回 False。
如果 len(s) == k，则可以直接使用单个字符构建回文串，直接返回 True。
如果 len(s) > k，则需要判断一下字符串 s 中每个字符的个数。因为当字符是偶数个时，可以直接构造成回文串。所以我们只需要考虑个数为奇数的字符即可。如果个位为奇数的字符种类小于等于 k，则说明可以构造 k 个回文串，返回 True。如果个位为奇数的字符种类大于 k，则说明无法构造 k 个回文串，返回 Fasle。

思路 1：贪心算法代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


import collections

class Solution:
    def canConstruct(self, s: str, k: int) -> bool:
        size = len(s)
        if size < k:
            return False
        if size == k:
            return True
        letter_dict = dict()
        for i in range(size):
            if s[i] in letter_dict:
                letter_dict[s[i]] += 1
            else:
                letter_dict[s[i]] = 1

        odd = 0
        for key in letter_dict:
            if letter_dict[key] % 2 == 1:
               odd += 1
        return odd <= k