1189. Maximum Number of Balloons - Explanation

Problem Link

1. Hash Map - I

Intuition

To form the word "balloon", we need specific counts of each letter: one each of 'b', 'a', 'n', and two each of 'l' and 'o'. The number of times we can spell "balloon" is limited by whichever required letter runs out first. By counting all letters in the text and then dividing by the required amounts, we find how many complete words we can form.

Algorithm

1. Count the frequency of each character in the input text using a hash map.
2. Create a hash map for the word "balloon" with the required count of each character.
3. For each character in "balloon", calculate how many times it can satisfy the requirement by dividing the available count by the required count.
4. Return the minimum across all characters, as this determines the bottleneck.

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        countText = Counter(text)
        balloon = Counter("balloon")

        res = len(text)
        for c in balloon:
            res = min(res, countText[c] // balloon[c])
        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ since we have at most $26$ different characters.

---

2. Hash Map - II

Intuition

We can optimize by only counting the five relevant characters ('b', 'a', 'l', 'o', 'n') instead of all 26 letters. After counting, we adjust for 'l' and 'o' by dividing their counts by 2 since each "balloon" requires two of each. The minimum count then gives our answer directly.

Algorithm

1. Iterate through the text and only count characters that appear in "balon" (the unique letters of "balloon").
2. If fewer than 5 distinct characters are counted, return 0 (cannot form even one "balloon").
3. Divide the counts of 'l' and 'o' by 2 to account for needing two of each.
4. Return the minimum value among all five character counts.

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        mp = defaultdict(int)
        for c in text:
            if c in "balon":
                mp[c] += 1

        if len(mp) < 5:
            return 0

        mp['l'] //= 2
        mp['o'] //= 2
        return min(mp.values())

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ since $balloon$ has $5$ different characters.

---

Common Pitfalls

Forgetting Double Letters

The word "balloon" contains two ls and two os. A common mistake is treating all characters equally without dividing the counts of l and o by 2. This results in overcounting the number of possible words that can be formed.

Not Checking for Missing Characters

If any of the five required characters (b, a, l, o, n) is missing from the text, the answer is 0. Failing to handle this case (for example, by taking the minimum of an empty collection or dividing by zero) can cause runtime errors or incorrect results.