1189.md

title	description	keywords
1189. “气球” 的最大数量	LeetCode 1189. “气球” 的最大数量题解，Maximum Number of Balloons，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 1189. “气球” 的最大数量 “气球” 的最大数量 Maximum Number of Balloons 解题思路 哈希表 字符串 计数

1189. “气球” 的最大数量

🟢 Easy  🔖  哈希表 字符串 计数  🔗 力扣 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;
};