原文链接: https://leetcode-cn.com/problems/maximum-number-of-balloons

英文原文

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 <= 104
• text consists of lower case English letters only.

中文题目

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

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

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

通过代码

高赞题解

解题思路

1. 哈希表存字符出现次数。
2. “balloon” 出现最少的即为结果。

代码

class Solution {
public:
    int maxNumberOfBalloons(string text) {
        unordered_map<char, int> c;
        for (char s : text) ++c[s];
        return min({c['b'], c['a'], c['l']/2, c['o']/2, c['o']});
    }
};

时间复杂度: O(n)
空间复杂度: O(n)

统计信息

通过次数	提交次数	AC比率
21698	33566	64.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言