Easy

题目描述

给你一个字符串 text，你需要使用 text 中的字母来尽可能多地拼凑单词 “balloon”。

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

注意： 这道题与题目 2287: 重新排列字符形成目标字符串 相同。

解题思路

这道题的核心思路是统计字符频率，然后找到限制因子。

要拼成单词 “balloon”，我们需要：

  • ‘b’: 1个
  • ‘a’: 1个
  • ’l’: 2个
  • ‘o’: 2个
  • ’n’: 1个

解题步骤：

  1. 统计字符频率：遍历输入字符串，统计每个字符的出现次数
  2. 计算最大拼凑数：对于每个必需的字符，计算可以满足多少个 “balloon”
    • 对于需要1个的字符（b、a、n）：直接用字符数量
    • 对于需要2个的字符（l、o）：用字符数量除以2
  3. 取最小值：所有字符能拼凑数量的最小值就是答案

这是一个经典的"木桶原理"问题，最终结果受限于最稀缺的资源。

时间复杂度为O(n)，空间复杂度为O(1)，因为我们只需要统计固定的几个字符。

代码实现

class Solution {
public:
    int maxNumberOfBalloons(string text) {
        // 统计字符频率
        int count[26] = {0};
        for (char c : text) {
            count[c - 'a']++;
        }
        
        // 计算每个字符能拼凑的balloon数量
        int b = count['b' - 'a'];
        int a = count['a' - 'a'];
        int l = count['l' - 'a'] / 2;  // l需要2个
        int o = count['o' - 'a'] / 2;  // o需要2个
        int n = count['n' - 'a'];
        
        // 返回最小值
        return min({b, a, l, o, n});
    }
};

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        from collections import Counter
        
        # 统计字符频率
        count = Counter(text)
        
        # 计算每个字符能拼凑的balloon数量
        b = count['b']
        a = count['a']
        l = count['l'] // 2  # l需要2个
        o = count['o'] // 2  # o需要2个
        n = count['n']
        
        # 返回最小值
        return min(b, a, l, o, n)

public class Solution {
    public int MaxNumberOfBalloons(string text) {
        // 统计字符频率
        int[] count = new int[26];
        foreach (char c in text) {
            count[c - 'a']++;
        }
        
        // 计算每个字符能拼凑的balloon数量
        int b = count['b' - 'a'];
        int a = count['a' - 'a'];
        int l = count['l' - 'a'] / 2;  // l需要2个
        int o = count['o' - 'a'] / 2;  // o需要2个
        int n = count['n' - 'a'];
        
        // 返回最小值
        return Math.Min(Math.Min(Math.Min(b, a), Math.Min(l, o)), n);
    }
}

var maxNumberOfBalloons = function(text) {
    // 统计字符频率
    const count = {};
    for (let c of text) {
        count[c] = (count[c] || 0) + 1;
    }
    
    // 计算每个字符能拼凑的balloon数量
    const b = count['b'] || 0;
    const a = count['a'] || 0;
    const l = Math.floor((count['l'] || 0) / 2);  // l需要2个
    const o = Math.floor((count['o'] || 0) / 2);  // o需要2个
    const n = count['n'] || 0;
    
    // 返回最小值
    return Math.min(b, a, l, o, n);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历一次字符串统计字符频率，其中n为字符串长度
空间复杂度O(1)只使用固定大小的数组或哈希表存储字符频率