Maximum Number of Balloons: Hash Map Frequency Counting
Given a string text, you want to form as many instances of the word "balloon" as possible using the characters from text. Each character in text can be used at most once. Return the maximum number of instances that can be formed.
This is LeetCode 1189: Maximum Number of Balloons, and it is one of the cleanest problems for practicing frequency counting with a hash map. The idea is simple, but it teaches a pattern you will see in dozens of other string problems.
Why this problem matters
Frequency counting is one of the most common building blocks in string and array problems. You will use it in anagram detection, character matching, sliding windows, and many more. Maximum Number of Balloons isolates the core skill: count how many of each character you have, then figure out how many complete "units" you can build from those counts.
Once you internalize this pattern here, you can apply it to problems like Ransom Note (LeetCode 383), Valid Anagram (LeetCode 242), and Find All Anagrams in a String (LeetCode 438).
The key insight
The word "balloon" uses five distinct characters: b (1), a (1), l (2), o (2), and n (1). Some characters appear once, others appear twice. To figure out how many complete "balloon" strings you can build, you count how many of each character the input provides, then divide each count by how many that character needs. The bottleneck is whichever character runs out first, so the answer is the minimum of all those divisions.
For example, if you have 4 l's and each "balloon" needs 2 l's, you can supply 2 balloons from l alone. But if you only have 1 a, you can only make 1 balloon total, because a runs out first.
The solution
from collections import Counter
def max_number_of_balloons(text: str) -> int:
count = Counter(text)
balloon = Counter("balloon")
return min(count[c] // balloon[c] for c in balloon)
The solution is three lines. Let's walk through each one.
Counter(text) builds a frequency map of every character in the input string. For "loonbalxballpoon", this produces something like {'l': 4, 'o': 3, 'n': 2, 'b': 2, 'a': 1, 'x': 1, 'p': 1}.
Counter("balloon") builds the frequency map for the target word: {'l': 2, 'o': 2, 'b': 1, 'a': 1, 'n': 1}. This tells us exactly how many of each character one "balloon" requires.
The final line iterates over each character in the target, divides the available count by the needed count using integer division, and returns the minimum. That minimum is the bottleneck, the character that limits how many complete "balloon" strings you can form.
Using Counter for both the input and the target makes the code generalizable. If the problem asked you to form "leetcode" instead of "balloon", you would change exactly one string. The logic stays the same.
Visual walkthrough
Let's trace through the input "loonbalxballpoon" step by step, from counting to dividing to finding the minimum.
Step 1: Scan the input string
Input: "loonbalxballpoon". Highlighted characters appear in "balloon".
Step 2: Count frequencies of balloon characters
Only b, a, l, o, n matter. All other characters (like x, p) are ignored.
Step 3: Divide each count by what one "balloon" needs
| Char | Available | Needed | Available / Needed |
|---|---|---|---|
| b | 2 | 1 | 2 |
| a | 1 | 1 | 1 |
| l | 4 | 2 | 2 |
| o | 3 | 2 | 1 |
| n | 2 | 1 | 2 |
For each character, compute floor(available / needed). The minimum across all five is the answer.
Step 4: Take the minimum ratio
min(2, 1, 2, 1, 2) = 1. We can form exactly 1 "balloon" from "loonbalxballpoon".
The walkthrough shows that both 'a' and 'o' are the limiting characters, each allowing only 1 balloon. Even though we have plenty of 'l' and 'b', the answer is constrained by the scarcest resource. This "minimum of ratios" pattern is the heart of the problem.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Frequency counting | O(n) | O(1) |
Time is O(n) where n is the length of the input string. We scan the string once to build the frequency map, then do a constant number of lookups (5 characters in "balloon"). The five divisions and the min operation are O(1).
Space is O(1) because the frequency map has at most 26 entries (one per lowercase letter). This does not grow with the input size. The target frequency map is also fixed at 5 entries.
The building blocks
1. Frequency counting with a hash map
The pattern of counting how many times each element appears in a collection:
from collections import Counter
count = Counter(text)
This is the same building block used in Valid Anagram, Group Anagrams, Ransom Note, and dozens of other problems. You scan the input once, storing counts in a dictionary. Lookups and updates are O(1) each. Whenever a problem mentions "how many," "enough," or "can you form," frequency counting is usually the first tool to reach for.
2. Computing the bottleneck with integer division
The pattern of determining how many complete units you can build from limited resources:
min(count[c] // needed[c] for c in needed)
This combines integer division with a minimum scan. For each required resource, you compute how many units that resource alone could support, then take the minimum. You see this pattern in manufacturing problems, resource allocation, and any scenario where multiple ingredients must all be present in specific ratios. The // operator handles the floor division automatically, ensuring you only count complete units.
Edge cases
- Empty string: no characters available, so the answer is 0.
Counter("")returns an empty map, andcount[c]defaults to 0 for anyc. - No balloon characters at all: for example,
"zzzzz". Every division produces 0, somin(...)returns 0. - Exactly one balloon:
"balloon"itself returns 1. Each character appears exactly as many times as needed. - Lots of repeated characters:
"bbbaaallllllooooonnnn"has b:3, a:3, l:6, o:5, n:4. Dividing gives 3, 3, 3, 2, 4. The minimum is 2 (limited by 'o'). - Single character repeated:
"llllll"returns 0 because b, a, o, and n are all missing.
From understanding to recall
You have seen how frequency counting solves Maximum Number of Balloons: count the characters, divide by what each one needs, and take the minimum. The logic is clean and the code fits in three lines. But reproducing it under pressure requires more than understanding.
The details that matter are small. Do you remember that 'l' and 'o' need 2 each, not 1? Do you use // for integer division or /? Do you iterate over the target characters or the input characters? These are the kinds of details that slip away if you only read the solution once.
Spaced repetition locks them in. You practice writing the frequency map, the division loop, and the min operation from memory at increasing intervals. After a few rounds, the pattern becomes automatic. You see "how many X can you form from Y" in a problem statement and the three-line template appears without hesitation.
Related posts
- Valid Anagram - The classic frequency counting problem where you compare two strings character by character
- Ransom Note - Another "can you build X from Y" problem using the same frequency map approach
- Find All Anagrams in a String - Extends frequency counting with a sliding window to find all anagram positions
CodeBricks breaks Maximum Number of Balloons into its frequency counting and bottleneck computation building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a frequency counting problem shows up in your interview, you do not think about it. You just write it.