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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Balloons

Number: 1297

Difficulty: Easy

Paid? No

Companies: Microsoft, Tesla, Amazon, Wayfair

Problem Description

Given a string text, determine the maximum number of times the word "balloon" can be formed using the characters in text. Each character in text can be used at most once.

Key Insights

  • Count the frequency of each character in the text.
  • The target word "balloon" requires:
    • b: 1
    • a: 1
    • l: 2
    • o: 2
    • n: 1
  • The number of times "balloon" can be formed is limited by the minimum value among these frequencies (taking into account that l and o are needed twice).

Space and Time Complexity

Time Complexity: O(n), where n is the length of text. Space Complexity: O(1), as the frequency count uses constant space (only lower-case English letters).

Solution

We first build a frequency map of characters in the input text using a hash table (or dictionary). For the word "balloon", we calculate the possible counts by taking:

  • The count of 'b'
  • The count of 'a'
  • The count of 'n'
  • The count of 'l' divided by 2 (since two are needed)
  • The count of 'o' divided by 2 (since two are needed)

The answer is the minimum of all these values, ensuring that all necessary characters are available in the required quantities. This approach is efficient due to single-pass counting and constant extra space.

Code Solutions

from collections import Counter

def maxNumberOfBalloons(text: str) -> int:
    # Count frequency of each character in the text.
    char_count = Counter(text)
    # Calculate the number of possible "balloon" words for each character, noting that 'l' and 'o' are needed twice.
    count_b = char_count.get('b', 0)
    count_a = char_count.get('a', 0)
    count_l = char_count.get('l', 0) // 2
    count_o = char_count.get('o', 0) // 2
    count_n = char_count.get('n', 0)
    # The maximum number of balloons is limited by the smallest count from required characters.
    return min(count_b, count_a, count_l, count_o, count_n)

# Example usage:
print(maxNumberOfBalloons("nlaebolko"))  # Output: 1
← Back to All Questions