Domain 1EasyCORE

Maximum Number of Balloons

The problem asks us to determine how many times we can form the word "balloon" using the characters from a given string `text`. Each character in `text` can be used at most once. The input is a single string consisting of lowercase English letters, and the output should be an integer representing the maximum number of instances of the word "balloon" that can be formed.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table#String

1189. Maximum Number of Balloons

Model: qwen2.5-coder:14b
Topics: Hash Table,String
FAANG asked: 0
Acceptance rate: 62.3%


Problem Breakdown

The problem asks us to determine how many times we can form the word “balloon” using the characters from a given string text. Each character in text can be used at most once. The input is a single string consisting of lowercase English letters, and the output should be an integer representing the maximum number of instances of the word “balloon” that can be formed.

Inputs:

  • A string text.

Outputs:

  • An integer representing the maximum number of times “balloon” can be formed.

Implicit Constraints or Tricky Edge Cases:

  • The input string may contain characters not present in “balloon”.
  • The input string could be empty, in which case no instances of “balloon” can be formed.
  • Characters that appear more than necessary (e.g., multiple ‘l’s or ‘o’s) should only count as many times as needed for one instance of “balloon”.

Intuition

A brute-force approach would involve checking every possible substring of text to see if it matches “balloon”, which is computationally expensive and impractical given the constraints. Instead, we can leverage a more efficient method by counting the occurrences of each character in “balloon” within the input string.

The key insight is that we need to count how many times each character required for “balloon” appears in text. The limiting factor will be the character with the fewest occurrences relative to its requirement in “balloon”. For example, if ‘o’ appears only once but ‘l’ appears three times, we can form at most one instance of “balloon”.

Approach

  1. Count Character Frequencies: Use a hash table (dictionary) to count the frequency of each character in text.
  2. Determine Limiting Factor: For each character required for “balloon”, determine how many instances of “balloon” can be formed based on its count in text. Special attention should be given to characters that appear more than once in “balloon” (i.e., ‘l’ and ‘o’).
  3. Return the Minimum Count: The result will be the minimum value obtained from step 2, as this represents the limiting factor.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input string text. We need to iterate through the string once to count character frequencies.
  • Space Complexity: O(1), since the hash table will have a fixed size (at most 7 unique characters: ‘b’, ‘a’, ‘l’, ‘o’, ‘n’).

Solution

def maxNumberOfBalloons(text: str) -> int:
    # Step 1: Count character frequencies in text
    char_count = {'b': 0, 'a': 0, 'l': 0, 'o': 0, 'n': 0}
    for char in text:
        if char in char_count:
            char_count[char] += 1
    
    # Step 2: Determine the number of balloons that can be formed
    # Each balloon requires 1 'b', 1 'a', 2 'l's, 2 'o's, and 1 'n'
    max_balloons = min(
        char_count['b'],
        char_count['a'],
        char_count['l'] // 2,
        char_count['o'] // 2,
        char_count['n']
    )
    
    return max_balloons

Edge Cases Handled

  • Empty Input: If text is empty, the function will return 0 because no characters are available to form “balloon”.
  • Insufficient Characters: If any character required for “balloon” is missing from text, the function will return 0.
  • Excess Characters: Characters that appear more than necessary (e.g., multiple ‘l’s or ‘o’s) are handled by integer division, ensuring they only count as many times as needed for one instance of “balloon”.