[1189] 气球的最大数量

题目描述

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

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

示例 1：

输入：text = "nlaebolko" 输出：1

示例 2：

输入：text = "loonbalxballpoon" 输出：2

示例 3：

输入：text = "leetcode" 输出：0

提示：

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

解题思路

这题的核心其实就一句话：能拼出多少个 "balloon"，取决于那个最缺的字母。

"balloon" 这个词里，b、a、n各需要 1 个，但l和o各需要 2 个。

所以思路很直接：

1. 先统计text里b、a、l、o、n这五个字母分别出现了多少次。
2. 因为l和o每次要用两个，所以它们能提供的"份数"是出现次数 // 2。
3. 最后取这五个值的最小值，就是答案。

min(cnt['b'], cnt['a'], cnt['l']//2, cnt['o']//2, cnt['n'])

时间复杂度 O(n)，空间复杂度 O(1)（只统计 5 个字符）。

完整代码

class Solution: def maxNumberOfBalloons(self, text: str) -> int: from collections import Counter cnt = Counter(text) return min(cnt['b'], cnt['a'], cnt['l'] // 2, cnt['o'] // 2, cnt['n'])