Maximum Number of Balloons

How it works

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.

Steps

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.

Complexity

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

Things to watch for

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.

from collections import defaultdict

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())

class Solution {
public:
    int maxNumberOfBalloons(string text) {
        unordered_map<char, int> mp;
        for (char c : text) {
            if (string("balon").find(c) != string::npos) {
                mp[c]++;
            }
        }

        if (mp.size() < 5) {
            return 0;
        }

        mp['l'] /= 2;
        mp['o'] /= 2;
        return min({mp['b'], mp['a'], mp['l'], mp['o'], mp['n']});
    }
};