1189 Maximum Number of Balloons “气球” 的最大数量
Description:
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:
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.
题目描述:
给你一个字符串 text，你需要使用 text 中的字母来拼凑尽可能多的单词 "balloon"（气球）。
字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 "balloon"。
示例 :
示例 1：
输入：text = "nlaebolko"
输出：1
示例 2：
输入：text = "loonbalxballpoon"
输出：2
示例 3：
输入：text = "leetcode"
输出：0
提示：
1 <= text.length <= 10^4
text 全部由小写英文字母组成
思路:
balloon由 1个 'b', 1个 'a', 2个 'l', 2个 'o', 1个 'n'组成, 只要找到这些字符的个数的最小值即可
时间复杂度O(n), 空间复杂度O(1)
代码:
C++:
class Solution
{
public:
int maxNumberOfBalloons(string text)
{
int count[26]{0}, index[]{0, 1, 11, 13, 14}, result = 10000;
for (auto c : text) ++count[c - 'a'];
count[11] /= 2;
count[14] /= 2;
for (auto i : index) result = min(result, count[i]);
return result;
}
};
Java:
class Solution {
public int maxNumberOfBalloons(String text) {
int count[] = new int[26], index[] = new int[]{0, 1, 11, 13, 14}, result = Integer.MAX_VALUE;
for (char c : text.toCharArray()) ++count[c - 'a'];
count[11] /= 2;
count[14] /= 2;
for (int i : index) result = Math.min(result, count[i]);
return result;
}
}
Python:
class Solution:
def maxNumberOfBalloons(self, text: str) -> int:
return min(collections.Counter(text)['b'], collections.Counter(text)['a'], collections.Counter(text)['l'] // 2, collections.Counter(text)['o'] // 2, collections.Counter(text)['n'])
