Maximum Number of Balloons
Last Updated: April 6, 2026
Understanding the Problem
We need to figure out how many times we can spell out "balloon" using the characters available in the input string. Each character in the string can only be used once.
The word "balloon" is interesting because not every letter appears the same number of times: b appears once, a appears once, l appears twice, o appears twice, and n appears once. So even if we have plenty of b's and a's, we need twice as many l's and o's to keep up.
The key observation is: the answer is bottlenecked by whichever required character is in shortest supply, after accounting for how many of that character each "balloon" needs.
Key Constraints:
1 <= text.length <= 10^4→ With n up to 10,000, even O(n^2) would work fine, but O(n) is the natural fit here since we just need to count characters.textconsists of lowercase English letters only → We only need to track 26 possible characters (or even just the 5 that matter: b, a, l, o, n).
Approach 1: Character Frequency with Array
Intuition
The most direct way to think about this: count every character in the string, then check how many complete "balloon"s we can assemble.
Since "balloon" uses b(1), a(1), l(2), o(2), n(1), we just need to count these five characters in the input. For 'l' and 'o', we divide their counts by 2 since each "balloon" consumes two of each. The bottleneck character, the one that runs out first, determines our answer.
Algorithm
- Create a frequency array of size 26 (one slot per lowercase letter) and count every character in the input string.
- Look up the counts for b, a, l, o, and n.
- Divide the count of 'l' by 2 and the count of 'o' by 2 (integer division), since each "balloon" needs two of each.
- Return the minimum of these five values.
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the string once to count characters. The five comparisons at the end are O(1).
- Space Complexity: O(1). The frequency array is fixed at size 26 regardless of input size.
This approach is already optimal in time and space, but the code is a bit verbose with all the individual character lookups. What if we generalized the logic so it works for any target word, not just "balloon"?
Approach 2: Hash Map with Target Word Frequency
Intuition
Instead of hardcoding the five character checks, we can generalize the approach. Count the characters in both the input text and the target word "balloon", then for each character in the target, compute how many times its supply covers its demand. The minimum across all characters is our answer.
This approach is cleaner and would work for any target word, not just "balloon".
Think of it like a factory assembly line. To build one "balloon", you need exactly 1 bolt-b, 1 bolt-a, 2 bolt-l's, 2 bolt-o's, and 1 bolt-n. Your warehouse (the input string) has a certain stock of each bolt. The number of complete products you can assemble is limited by whichever bolt runs out first. Dividing supply by demand for each bolt and taking the minimum gives you exactly that bottleneck.
Algorithm
- Build a frequency map for the input string.
- Build a frequency map for the word "balloon".
- For each character in "balloon"'s frequency map, divide the input count by the required count.
- Return the minimum of all these divisions.
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the input string once to build the frequency map. The loop over "balloon"'s unique characters is O(1) since it's always 5 characters.
- Space Complexity: O(1). Both hash maps are bounded by the alphabet size (26 lowercase letters), so space is constant regardless of input length.