跳转至

1189. “气球” 的最大数量

题目描述

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

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

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

解法

方法一：计数

我们统计字符串 text 中每个字母出现的次数，然后将其中字母 'o' 和 'l' 的出现次数分别除以 2，这是因为单词 balloon 中字母 'o' 和 'l' 都出现了 2 次。

接着，我们遍历单词 balon 中的每个字母，统计每个字母在字符串 text 中出现的次数的最小值，这个最小值就是单词 balloon 在字符串 text 中出现的最大次数。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 为字符串 text 的长度；而 $C$ 为字符集大小，本题中 $C = 26$。

1
2
3
4
5
6
class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        cnt = Counter(text)
        cnt['o'] >>= 1
        cnt['l'] >>= 1
        return min(cnt[c] for c in 'balon')

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int maxNumberOfBalloons(String text) {
        int[] cnt = new int[26];
        for (int i = 0; i < text.length(); ++i) {
            ++cnt[text.charAt(i) - 'a'];
        }
        cnt['l' - 'a'] >>= 1;
        cnt['o' - 'a'] >>= 1;
        int ans = 1 << 30;
        for (char c : "balon".toCharArray()) {
            ans = Math.min(ans, cnt[c - 'a']);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxNumberOfBalloons(string text) {
        int cnt[26]{};
        for (char c : text) {
            ++cnt[c - 'a'];
        }
        cnt['o' - 'a'] >>= 1;
        cnt['l' - 'a'] >>= 1;
        int ans = 1 << 30;
        string t = "balon";
        for (char c : t) {
            ans = min(ans, cnt[c - 'a']);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func maxNumberOfBalloons(text string) int {
    cnt := [26]int{}
    for _, c := range text {
        cnt[c-'a']++
    }
    cnt['l'-'a'] >>= 1
    cnt['o'-'a'] >>= 1
    ans := 1 << 30
    for _, c := range "balon" {
        if x := cnt[c-'a']; ans > x {
            ans = x
        }
    }
    return ans
}

1
2
3
4
5
6
7
function maxNumberOfBalloons(text: string): number {
    const cnt = new Array(26).fill(0);
    for (const c of text) {
        cnt[c.charCodeAt(0) - 97]++;
    }
    return Math.min(cnt[0], cnt[1], cnt[11] >> 1, cnt[14] >> 1, cnt[13]);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
impl Solution {
    pub fn max_number_of_balloons(text: String) -> i32 {
        let mut arr = [0; 5];
        for c in text.chars() {
            match c {
                'b' => {
                    arr[0] += 1;
                }
                'a' => {
                    arr[1] += 1;
                }
                'l' => {
                    arr[2] += 1;
                }
                'o' => {
                    arr[3] += 1;
                }
                'n' => {
                    arr[4] += 1;
                }
                _ => {}
            }
        }
        arr[2] /= 2;
        arr[3] /= 2;
        let mut res = i32::MAX;
        for num in arr {
            res = res.min(num);
        }
        res
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    /**
     * @param String $text
     * @return Integer
     */
    function maxNumberOfBalloons($text) {
        $cnt1 = $cnt2 = $cnt3 = $cnt4 = $cnt5 = 0;
        for ($i = 0; $i < strlen($text); $i++) {
            if ($text[$i] == 'b') {
                $cnt1 += 1;
            } elseif ($text[$i] == 'a') {
                $cnt2 += 1;
            } elseif ($text[$i] == 'l') {
                $cnt3 += 1;
            } elseif ($text[$i] == 'o') {
                $cnt4 += 1;
            } elseif ($text[$i] == 'n') {
                $cnt5 += 1;
            }
        }
        $cnt3 = floor($cnt3 / 2);
        $cnt4 = floor($cnt4 / 2);
        return min($cnt1, $cnt2, $cnt3, $cnt4, $cnt5);
    }
}

评论