LeetCode 1189 - Maximum Number of Balloons

Difficulty: 🟢 Easy
Topics: Hash Table, String, Counting

Solution

Problem Understanding

The problem asks us to determine the maximum number of times the word "balloon" can be formed using the characters from a given string text. Each character in text can be used at most once per occurrence of the word. The input is a string consisting of only lowercase English letters, with length up to 10,000. The output is an integer representing the maximum number of instances of "balloon" that can be constructed.

Restated in other words, we are essentially counting the frequency of the letters required for the word "balloon"-specifically, 'b', 'a', 'l', 'o', and 'n'. Because 'l' and 'o' appear twice in "balloon", we must account for that in the calculation. The maximum number of times "balloon" can be formed is constrained by the letter whose available count (after adjusting for duplicates) is the smallest.

Important edge cases include input strings that do not contain some of the required letters, strings that contain just enough letters to form a single "balloon", and strings with excessive letters, where the limiting factor will be the letters that appear fewer times.

Approaches

The brute-force approach would involve repeatedly checking if "balloon" can be formed from the current character counts and decrementing the counts each time. While this is correct, it is inefficient because it could require O(n * m) operations, where n is the length of the string and m is the number of times "balloon" can be formed. This approach is unnecessary given the insight that the problem reduces to counting character frequencies.

The optimal approach leverages a frequency counter (hash map) to count the occurrence of each character in text. Then, for each letter in "balloon", we calculate how many times it can contribute to forming the word, taking into account the duplicate letters 'l' and 'o'. The answer is the minimum count across all required letters, after dividing the counts of 'l' and 'o' by 2 (since they appear twice per word).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(1)	Repeatedly form "balloon" until impossible
Optimal	O(n)	O(1)	Count frequencies, adjust for duplicates, take minimum

Algorithm Walkthrough

Initialize a dictionary or hash map to count the occurrences of each character in text.
Iterate over each character in text and update the frequency counter.
For the word "balloon", create a mapping of required counts: 'b':1, 'a':1, 'l':2, 'o':2, 'n':1.
For each required character, calculate how many complete contributions it can make by dividing the frequency in text by the required count.
Return the minimum of these values as the maximum number of times "balloon" can be formed.

Why it works: The invariant here is that forming "balloon" requires all letters in fixed amounts. The maximum number of words is limited by the scarcest adjusted letter. By calculating this minimum, we ensure that no letter is overused, guaranteeing correctness.

Python Solution

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        from collections import Counter

        freq = Counter(text)
        required = {'b': 1, 'a': 1, 'l': 2, 'o': 2, 'n': 1}

        # For each required letter, calculate how many times it can contribute to "balloon"
        return min(freq.get(char, 0) // count for char, count in required.items())

The implementation first uses Counter to count occurrences of each character. Then it defines the required counts for "balloon". The minimum of the integer division of available counts by required counts gives the number of complete words that can be formed. Using freq.get(char, 0) ensures that missing letters return 0, handling edge cases.

Go Solution

func maxNumberOfBalloons(text string) int {
    freq := make(map[rune]int)
    for _, ch := range text {
        freq[ch]++
    }

    required := map[rune]int{'b': 1, 'a': 1, 'l': 2, 'o': 2, 'n': 1}
    minCount := int(^uint(0) >> 1) // Max int

    for ch, count := range required {
        available := freq[ch] / count
        if available < minCount {
            minCount = available
        }
    }
    return minCount
}

In Go, we use a map[rune]int to count character occurrences. We iterate over the required letters and divide their counts by the number needed. The smallest resulting value is returned. Go does not have a built-in Counter, so a simple map suffices. Max int is initialized using bit manipulation to ensure proper minimum comparison.

Worked Examples

Example 1: text = "nlaebolko"

Letter	Count in text	Required	Adjusted count
b	1	1	1
a	1	1	1
l	2	2	1
o	2	2	1
n	1	1	1

Minimum adjusted count is 1, so output is 1.

Example 2: text = "loonbalxballpoon"

Letter	Count in text	Required	Adjusted count
b	2	1	2
a	2	1	2
l	4	2	2
o	4	2	2
n	2	1	2

Minimum adjusted count is 2, so output is 2.

Example 3: text = "leetcode"

Letter	Count in text	Required
b	0	1
a	0	1
l	1	2
o	1	2
n	0	1

Minimum adjusted count is 0, so output is 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We traverse the input string once to count letters, where n is the length of text
Space	O(1)	Maximum of 26 lowercase letters stored in the frequency map, so constant space

The algorithm is efficient because it only counts letters and performs a fixed number of calculations based on the 5 unique letters of "balloon".

Test Cases

# Provided examples
assert Solution().maxNumberOfBalloons("nlaebolko") == 1  # single instance
assert Solution().maxNumberOfBalloons("loonbalxballpoon") == 2  # two instances
assert Solution().maxNumberOfBalloons("leetcode") == 0  # cannot form

# Edge cases
assert Solution().maxNumberOfBalloons("balloon") == 1  # exact one occurrence
assert Solution().maxNumberOfBalloons("balloonballoon") == 2  # exact two occurrences
assert Solution().maxNumberOfBalloons("bbaallllooonn") == 1  # excess letters but limited by duplicates
assert Solution().maxNumberOfBalloons("b"*1000 + "a"*1000 + "l"*2000 + "o"*2000 + "n"*1000) == 1000  # stress test
assert Solution().maxNumberOfBalloons("") == 0  # empty string

Test	Why
"nlaebolko"	Checks basic case of forming one word
"loonbalxballpoon"	Checks multiple instances and scattered letters
"leetcode"	Checks case with insufficient letters
"balloon"	Checks exact match for one word
"balloonballoon"	Checks exact match for two words
"bbaallllooonn"	Checks handling of duplicate letters
Large repeated letters	Checks algorithm with high input volume
""	Checks empty input edge case

Edge Cases

One important edge case is an empty string. Since no letters are present, the algorithm correctly returns 0 without errors because the frequency dictionary will be empty, and the min calculation will default to 0 for missing letters.

Another edge case is when the string contains some, but not all, letters needed for "balloon". For instance, "balon" has missing duplicates, so the algorithm will correctly compute the adjusted counts and return 0 if any required letter is missing.

A third edge case is when the counts of letters required more than once ('