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:贪心算法 #
- 用字符串
s
中所有字符构造回文串最多可以构造len(s)
个(将每个字符当做一个回文串)。所以如果len(s) < k
,则说明字符数量不够,无法构成k
个回文串,直接返回False
。 - 如果
len(s) == k
,则可以直接使用单个字符构建回文串,直接返回True
。 - 如果
len(s) > k
,则需要判断一下字符串s
中每个字符的个数。因为当字符是偶数个时,可以直接构造成回文串。所以我们只需要考虑个数为奇数的字符即可。如果个位为奇数的字符种类小于等于k
,则说明可以构造k
个回文串,返回True
。如果个位为奇数的字符种类大于k
,则说明无法构造k
个回文串,返回Fasle
。
思路 1:贪心算法代码 #
|
|