Max Number of Balloons LeetCode 1189

LeetCode 1189 — Maximum Number of Balloons — gives you a string text and asks you to return the maximum number of times the word "balloon" can be formed using the characters of text. Each character in text may be used at most once per instance of "balloon" formed.

For example, given text = "nlaebolko", the answer is 1. Given text = "loonbalxballpoon", the answer is 2. Given text = "leetcode", the answer is 0 because there is no "b" in "leetcode". The challenge is tracking which characters are limiting your count.

This is an Easy-rated problem that reinforces a core string frequency pattern: count occurrences of each required character, normalize by the number of times that character appears in the target word, and take the minimum across all required characters.

The word "balloon" requires exactly these characters: b appears 1 time, a appears 1 time, l appears 2 times, o appears 2 times, and n appears 1 time. The letters e, i, and other unused letters are irrelevant — you only need to track b, a, l, o, n in the input text.

To find how many balloons you can form, count how many of each required character appears in text. Then divide each count by the number of times that character is required per balloon. For b, a, n divide by 1. For l and o divide by 2. The minimum quotient (using integer division) across all five characters is your answer.

This approach works in O(n) time for the counting step and O(1) space since you only track 5 characters regardless of input size. The division step is constant work — 5 divisions and a single minimum call.

Use a Counter (Python) or HashMap (Java) on the full text string to get counts for every character present. You only care about the five characters in "balloon": b, a, l, o, n. All other characters can be ignored or simply left in the map unused.

Once you have the counts, the normalization is straightforward: count_b stays as-is (needed once), count_a stays as-is (needed once), count_l is divided by 2 (needed twice), count_o is divided by 2 (needed twice), count_n stays as-is (needed once). Use integer (floor) division throughout — you cannot form a fraction of a balloon.

If any required character is completely absent from text, its count will be 0. Dividing 0 by any requirement gives 0. The minimum will then be 0, correctly indicating that no complete "balloon" can be formed.

After normalization, the result is simply: min(count_b // 1, count_a // 1, count_l // 2, count_o // 2, count_n // 1). This minimum is the bottleneck character — the one that limits how many complete "balloon" strings you can assemble, regardless of how abundant the other characters are.

If text = "balloonballoon", you have b=2, a=2, l=4, o=4, n=2. After division: l→2, o→2. The minimum across {2, 2, 2, 2, 2} is 2. You can form exactly 2 balloons. Every character is consumed perfectly with no waste in this case.

If text = "bbbaaannn", you have b=3, a=3, n=3 but l=0 and o=0. After division: l→0, o→0. The minimum is 0. Despite having plenty of b, a, and n, you cannot form a single balloon because the l and o characters are completely absent.

Take text = "loonbalxballpoon". Let's count: b appears at positions 4 and 9 → b=2. a appears at positions 5 and 10 → a=2. l appears at positions 0, 8, 9, 11 → l=4. o appears at positions 1, 2, 12, 13 → o=4. n appears at positions 14 and implicitly — wait, let's recount. l-o-o-n-b-a-l-x-b-a-l-l-p-o-o-n: n at index 3 and index 15 → n=2. x and p are irrelevant.

Normalized counts: b=2 (÷1=2), a=2 (÷1=2), l=4 (÷2=2), o=4 (÷2=2), n=2 (÷1=2). All five normalized values equal 2. The minimum is 2. We can form exactly 2 complete "balloon" strings from this input.

Verify: first balloon uses b[0], a[0], l[0], l[1], o[0], o[1], n[0]. Second balloon uses b[1], a[1], l[2], l[3], o[2], o[3], n[1]. Every needed character is consumed, none left over. The answer of 2 is confirmed.

Python using Counter: from collections import Counter; def maxNumberOfBalloons(text): c = Counter(text); return min(c["b"], c["a"], c["l"] // 2, c["o"] // 2, c["n"]). Counter auto-initializes missing keys to 0 so no KeyError. This is O(n) time and O(1) space since the Counter has at most 26 entries.

Java approach: int[] freq = new int[26]; for (char ch : text.toCharArray()) freq[ch - 'a']++; return Math.min(freq['b'-'a'], Math.min(freq['a'-'a'], Math.min(freq['l'-'a']/2, Math.min(freq['o'-'a']/2, freq['n'-'a']))));. Using a fixed int[26] array instead of a HashMap gives O(1) space with no hashing overhead.

Both solutions run in O(n) time where n is the length of text, and O(1) space. The Python Counter allocates a small dict (at most 26 entries), while the Java array is always exactly 26 integers. Neither scales with input size beyond the constant character alphabet.

Maximum Number of Balloons belongs to the string frequency and character matching family. Valid Anagram (LeetCode 242) is the closest relative: it checks whether two strings have identical character frequencies — essentially a zero-difference version of the same frequency comparison. Ransom Note (LeetCode 383) asks whether magazine's character frequencies can satisfy note's requirements, which is the same supply-meets-demand structure.

Longest Palindrome (LeetCode 409) uses character frequencies to determine how long a palindrome you can build: every even-frequency character contributes fully, odd-frequency characters contribute count-1 (with one possible center character). The frequency-division minimum pattern from LeetCode 1189 appears in Reorganize String (LeetCode 767) and Task Scheduler (LeetCode 621) where you must check whether any character's frequency exceeds a threshold.

The core skill across all these problems is the same: build a frequency map in O(n), then reason about the ratios or differences between supply (source frequencies) and demand (target requirements). Mastering LeetCode 1189 builds the intuition for the entire character-count and string-matching family.