Maximum Number of Balloons

easy LeetCode #1189

hash-table string counting

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 1:
Input: text = "nlaebolko"
Output: 1
Explanation: The string contains the letters b, a, l, l, o, o, n (with one extra l, e, k). We can form one "balloon".

Example 2:
Input: text = "loonbalxballpoon"
Output: 2
Explanation: We have: b=2, a=2, l=4, o=4, n=2. Since "balloon" needs b=1, a=1, l=2, o=2, n=1, we can form 2 instances.

Example 3:
Input: text = "leetcode"
Output: 0
Explanation: The string doesn't contain 'b', so we cannot form any "balloon".

Constraints

1 <= text.length <= 10^4
text consists of lower case English letters only

Complexity

Show Complexity

Time: O(n)
Space: O(1)

Hints

Show Hints

Pattern: Hash map counting with limiting factor
Approach: Count each letter. For 'l' and 'o', divide by 2 since they appear twice in 'balloon'. Return the minimum count.
Complexity: Count frequencies of b, a, l, o, n. The answer is limited by the minimum ratio.

Solutions

Show PY Solution

from collections import defaultdict


def solution(text: str) -> int:
    m = defaultdict(int)

    for c in text:
        if c == "b" or c == "a" or c == "l" or c == "n" or c == "o":
            m[c] += 1

    sing_count = float("inf")
    all_exist = len(m) == 5
    l = 0
    o = 0
    for c, v in m.items():
        if c == "b" or c == "a" or c == "n":
            sing_count = min(sing_count, v)
        if c == "l":
            l += v
        if c == "o":
            o += v

    if not all_exist:
        return 0

    return min(int(sing_count), l // 2, o // 2)