Maximum Number of Balloons - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

Understand the problem: Find the maximum number of times the word "balloon" can be formed from a given text.
Initialize a defaultdict to count the frequency of characters in the text.
Iterate through each character in the text; if it is in "balloon" (i.e., one of 'b', 'a', 'l', 'o', 'n'), increment its count in the dictionary.
Check if all required characters ('b', 'a', 'l', 'o', 'n') are present in the dictionary; if any are missing, return 0.
Calculate the minimum of the counts for 'b', 'a', 'l' divided by 2, 'o' divided by 2, and 'n', as each "balloon" requires one 'b', one 'a', two 'l's, two 'o's, and one 'n'.
Return this minimum as the maximum number of "balloon" instances possible.

Code Solution

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        counter = defaultdict(int)
        balloon = "balloon"
        
        for c in text:
            if c in balloon:
                counter[c] += 1
        
        if any(c not in counter for c in balloon):
            return 0
        else:
            return min(counter["b"], counter["a"], counter["l"] // 2, counter["o"] // 2, counter["n"])

# Time Complexity: O(n)
# Space Complexity: O(1)

#include <unordered_map>
#include <algorithm>
#include <string>
using namespace std;

class Solution {
public:
    int maxNumberOfBalloons(string text) {
        unordered_map<char, int> counter;
        string balloon = "balloon";

        for (char c : text) {
            if (balloon.find(c) != string::npos) {
                counter[c]++;
            }
        }

        if (counter.find('b') == counter.end() || 
            counter.find('a') == counter.end() || 
            counter.find('l') == counter.end() || 
            counter.find('o') == counter.end() || 
            counter.find('n') == counter.end()) {
            return 0;
        } else {
            return min({counter['b'], counter['a'], counter['l'] / 2, counter['o'] / 2, counter['n']});
        }
    }
};

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxNumberOfBalloons(String text) {
        Map<Character, Integer> counter = new HashMap<>();
        String balloon = "balloon";

        for (char c : text.toCharArray()) {
            if (balloon.indexOf(c) != -1) {
                counter.put(c, counter.getOrDefault(c, 0) + 1);
            }
        }

        if (!counter.containsKey('b') || 
            !counter.containsKey('a') || 
            !counter.containsKey('l') || 
            !counter.containsKey('o') || 
            !counter.containsKey('n')) {
            return 0;
        } else {
            return Math.min(Math.min(counter.get('b'), counter.get('a')), 
                            Math.min(counter.get('l') / 2, 
                                     Math.min(counter.get('o') / 2, counter.get('n'))));
        }
    }
}

var maxNumberOfBalloons = function(text) {
    const counter = {};
    const balloon = "balloon";

    for (const c of text) {
        if (balloon.includes(c)) {
            counter[c] = (counter[c] || 0) + 1;
        }
    }

    if (!('b' in counter) || 
        !('a' in counter) || 
        !('l' in counter) || 
        !('o' in counter) || 
        !('n' in counter)) {
        return 0;
    } else {
        return Math.min(counter['b'], counter['a'], Math.floor(counter['l'] / 2), Math.floor(counter['o'] / 2), counter['n']);
    }
};

Detailed Explanation

Understanding the Problem: Maximum Number of Balloons

The “Maximum Number of Balloons” problem asks us to determine how many times the word "balloon" can be formed from the letters in a given input string text. Each instance of the word "balloon" requires the following characters: one 'b', one 'a', two 'l''s, two 'o''s, and one 'n'.

For example, given the input "loonbalxballpoon", we can form the word "balloon" twice.

Why This Problem Matters

This problem tests your ability to perform character frequency analysis and enforce resource constraints—an important pattern in string manipulation problems. It's directly applicable to scenarios such as resource allocation, recipe management, and string construction problems.

Approach: Frequency Counting

The key to solving this problem efficiently is to count how many times each required letter appears in the input and determine how many full sets of "balloon" we can extract from it.

Steps:

Initialize a hash map (or dictionary) to keep track of the frequency of each character in text.
Loop through each character in text. If the character is one of the required ones (i.e., in "balloon"), increment its count in the dictionary.
After populating the frequency map, check that all required characters exist. If any are missing, return 0 immediately.
Since the word "balloon" uses 'l' and 'o' twice, divide their frequencies by 2 (using integer division).
Take the minimum value among the adjusted counts for 'b', 'a', 'l' // 2, 'o' // 2, and 'n'. This minimum represents how many full "balloon" words we can construct.
Return that minimum count.

Example Walkthrough

Input: "balonbalonbal"
Frequencies:

'b' → 2
'a' → 2
'l' → 2
'o' → 2
'n' → 2

Adjusted frequencies:

'l' → 2 // 2 = 1
'o' → 2 // 2 = 1

Minimum of [2, 2, 1, 1, 2] = 1 → return 1.

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input string. We scan the string once to count character frequencies.
Space Complexity: O(1), because the frequency dictionary has a fixed size, limited to at most 26 lowercase English letters.

Edge Cases to Consider

If text is empty → return 0
If text lacks even one of the required characters → return 0
Extra characters in text that aren't part of "balloon" → ignore them

Conclusion

The “Maximum Number of Balloons” problem is an elegant example of frequency-based character matching. It teaches how to count occurrences and apply minimum constraints across multiple requirements. This is a valuable pattern in a wide range of string construction and inventory-based problems.

Get Personalized Support at AlgoMap Bootcamp 💡