Maximum Number of Balloons
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.
Not every letter in "balloon" appears the same number of times: b appears once, a appears once, l appears twice, o appears twice, and n appears once. So having plenty of b's and a's is not enough on its own. We need twice as many l's and o's to match them.
This makes the answer a bottleneck problem. We can build one "balloon" for every copy of each required character we have, after dividing the l and o counts by 2. Whichever character runs out first caps the total.
Key Constraints:
1 <= text.length <= 10^4→ Counting characters in a single pass is O(n), which is comfortable at this size. There is no need for anything fancier.textconsists of lowercase English letters only → We only need to track 26 possible characters, and only 5 of them (b, a, l, o, n) affect the answer.
Approach 1: Character Frequency with Array
Intuition
Count every character in the string, then check how many complete "balloon"s those characters can assemble.
Since "balloon" uses b(1), a(1), l(2), o(2), n(1), only these five characters matter. For 'l' and 'o', we divide their counts by 2 because each "balloon" consumes two of each. The character that runs out first determines the 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 is already optimal in time and space. The one drawback is that the five hardcoded character lookups only work for "balloon". The next approach expresses the same logic in terms of the target word itself, so it generalizes to any word.
Approach 2: Hash Map with Target Word Frequency
Intuition
Instead of hardcoding the five character checks, count the characters in both the input text and the target word "balloon". Then for each character the target needs, divide its supply (count in the text) by its demand (count in the target). The minimum across all those divisions is the answer. The only change from Approach 1 is that the per-character divisor comes from the target word instead of being written out by hand, so the same code handles any target word.
Building k copies of "balloon" requires k times the demand of every character at once, drawing from a shared pool. For a character with supply s and demand d, the most copies it can support is floor(s / d), since each copy spends d of it and characters are never refunded. Taking the minimum of floor(s / d) over all required characters gives the largest k that every character can satisfy simultaneously.
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.