We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Balloons

Difficulty: Easy

Problem Description

Given a string text, you want to use the characters of text to form as many instances of the word "balloon" as possible. You can use each character in text at most once. Return the maximum number of instances that can be formed.

Key Insights

  • The word "balloon" consists of the characters: b, a, l, o, n.
  • The letters 'l' and 'o' appear twice in the word "balloon", while the others appear once.
  • To determine how many times we can form "balloon", we need to count the occurrences of each of the required characters in text.
  • The limiting factor will be the character with the minimum ratio of available letters to required letters.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string text. Space Complexity: O(1), since we are using a fixed-size array/hash map to count characters.

Solution

To solve this problem, we can utilize a hash table (or a dictionary) to count the occurrences of each character in the input string. Then, we will compute how many complete sets of the characters needed to form the word "balloon" can be made by checking the counts of each character against its requirement in the word.

Code Solutions

def maxNumberOfBalloons(text: str) -> int:
    # Count occurrences of each letter in the text
    count = {}
    for char in text:
        count[char] = count.get(char, 0) + 1
    
    # Calculate the maximum number of "balloon" we can form
    # Required counts for "balloon": b=1, a=1, l=2, o=2, n=1
    return min(count.get('b', 0), 
               count.get('a', 0), 
               count.get('l', 0) // 2, 
               count.get('o', 0) // 2, 
               count.get('n', 0))
← Back to All Questions