1189. “气球” 的最大数量

🟢   🔖  哈希表 字符串 计数  🔗 力扣 LeetCode

题目

Given a string text, you want to use the characters of text to form as many instances of the word " balloon" as possible.

You can use each character in text at most once. Return the maximum number of instances that can be formed.

Example 1:

Input: text = "nlaebolko"

Output: 1

Example 2:

Input: text = "loonbalxballpoon"

Output: 2

Example 3:

Input: text = "leetcode"

Output: 0

Constraints:

• 1 <= text.length <= 10^4
• text consists of lower case English letters only.

Note: This question is the same as 2287. Rearrange Characters to Make Target String

题目大意

给你一个字符串 text，你需要使用 text 中的字母来拼凑尽可能多的单词 "balloon"（气球） 。

字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 "balloon" 。

示例 1：


输入： text = "nlaebolko"

输出： 1

示例 2：


输入： text = "loonbalxballpoon"

输出： 2

示例 3：

输入： text = "leetcode"

输出： 0

提示：

• 1 <= text.length <= 10^4
• text 全部由小写英文字母组成

注意： 本题与 2287. 重排字符形成目标字符串 相同。

解题思路

1. 字母频率统计： 通过一个哈希表 freq 来统计每个字母在 text 中出现的次数。
2. 计算拼凑次数： 对于 "balloon" 中的每个字母，检查它在 text 中的数量，并根据其在 "balloon" 中出现的次数来计算最大拼接次数。
   • 对于字母 'l' 和 'o'，它们在 "balloon" 中出现了两次，因此用 Math.floor(freq[char] / 2) 来计算它们的可拼凑次数。
3. 返回最小值： 最终返回最小的拼接次数，因为某个字母的数量可能限制了拼接次数。

复杂度分析

• 时间复杂度：O(n)，其中 n 是 text 的长度，统计 text 中的字母频率需要遍历一次字符串。

• 空间复杂度：O(1)，使用一个哈希表 freq 来存储每个字母的频率，最多有 26 个字母。

代码

/**
 * @param {string} text
 * @return {number}
 */
var maxNumberOfBalloons = function (text) {
	// 统计字母频率
	let freq = new Map();
	for (let char of text) {
		freq.set(char, (freq.get(char) || 0) + 1);
	}

	// 用于记录最小的拼凑次数
	let minCount = Infinity;
	// 计算可以拼凑的 "balloon" 的个数
	for (let char of charSet) {
		// 如果有任何字母在 text 中没有出现，直接返回 0
		if (!freq.has(char)) return 0;
		if (char === 'l' || char === 'o') {
			// 'l' 和 'o' 出现次数是 2
			minCount = Math.min(minCount, Math.floor(freq.get(char) / 2));
		} else {
			minCount = Math.min(minCount, freq.get(char));
		}
	}
	return minCount;
};