1400. 构造 K 个回文字符串

🟠   🔖  贪心 哈希表 字符串 计数  🔗 力扣 LeetCode

题目

Given a string s and an integer k, return true if you can use all the characters ins to constructk palindrome strings orfalseotherwise.

Example 1:

Input: s = "annabelle", k = 2

Output: true

Explanation: You can construct two palindromes using all characters in s.

Some possible constructions "anna" + "elble", "anbna" + "elle", "anellena" + "b"

Example 2:

Input: s = "leetcode", k = 3

Output: false

Explanation: It is impossible to construct 3 palindromes using all the characters of s.

Example 3:

Input: s = "true", k = 4

Output: true

Explanation: The only possible solution is to put each character in a separate string.

Constraints:

• 1 <= s.length <= 10^5
• s consists of lowercase English letters.
• 1 <= k <= 10^5

题目大意

给你一个字符串 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

解题思路

1. 回文串的性质：

   • 回文串中，字符出现奇数次的个数最多为 1（单个字符可以处于回文中心），其他字符必须出现偶数次。
   • 例如：
     • aabb 是回文，奇数次的字符为 0 个。
     • abcba 是回文，奇数次的字符为 1 个。
   • 如果允许多个回文串，字符出现奇数次的个数不能超过回文串的个数。

2. 贪心分配：

   • 使用 Map 或数组统计每个字符的出现次数。
   • 遍历频率表，记录出现奇数次的字符数量 count。
   • 每个出现奇数次的字符可以单独放入一个回文串中。
   • 如果奇数次的字符数量 count 大于 k，无法构造出 k 个回文串。
   • 如果字符串的长度小于 k，也无法构造。

3. 条件判断：

   • 如果字符串的长度 s.length 小于 k，返回 false。
   • 如果奇数次字符的数量 count 大于 k，返回 false。

复杂度分析

• 时间复杂度：O(n)，统计字符频率需要遍历字符串。
• 空间复杂度：O(1)，使用 Map 存储字符频率，最多存储 26 个字符。

代码

/**
 * @param {string} s
 * @param {number} k
 * @return {boolean}
 */
var canConstruct = function (s, k) {
	// 统计字符频率
	let map = new Map();
	for (let char of s) {
		map.set(char, (map.get(char) || 0) + 1);
	}

	// 计算出现奇数次的字符数量
	let count = 0;
	for (let value of map.values()) {
		if (value % 2 === 1) {
			count++;
		}
	}

	// 判断条件
	return s.length >= k && count <= k;
};