#1189

Easy

LeetCode Problem Workspace

Maximum Number of Balloons

Find the maximum number of times the word 'balloon' can be formed from characters of the given string.

Problem Statement

Given a string text, you need to determine how many times you can form the word 'balloon' using the characters in text. Each character in text can be used at most once. The word 'balloon' consists of the letters 'b', 'a', 'l', 'o', 'n', where the letter 'l' appears twice, and the letter 'o' appears twice.

Return the maximum number of instances of the word 'balloon' that can be formed from the characters of text. If it's not possible to form the word even once, return 0.

Examples

Example 1

Input: text = "nlaebolko"

Output: 1

Example details omitted.

Example 2

Input: text = "loonbalxballpoon"

Output: 2

Example details omitted.

Example 3

Input: text = "leetcode"

Output: 0

Example details omitted.

Constraints

1 <= text.length <= 104
text consists of lower case English letters only.

Solution Approach

Count Character Frequencies

Use a hash table (or dictionary) to count the frequency of each character in the input string text. Focus on the characters 'b', 'a', 'l', 'o', and 'n', as these are the only relevant characters for forming the word 'balloon'.

Calculate Maximum Possible Instances

For each of the characters 'b', 'a', 'l', 'o', and 'n', calculate how many complete instances of 'balloon' can be formed by dividing the frequency of each character by its required count in the word (2 for 'l' and 'o', 1 for others). The minimum value among these counts will determine the number of full 'balloon' instances.

Return the Result

The result is simply the minimum number of times 'balloon' can be formed, which can be computed efficiently by finding the smallest value in the list of computed frequencies for the relevant characters.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution is O(n), where n is the length of the input string text, as we need to iterate over all characters once to count their frequencies. The space complexity is O(1), since we only store a fixed number of characters in the hash table, independent of the size of text.

What Interviewers Usually Probe

The candidate identifies the need for frequency counting of characters relevant to 'balloon'.
The candidate efficiently computes the minimum number of 'balloon' instances from the character frequencies.
The candidate optimizes space by using a fixed-size hash table for character counts.

Common Pitfalls or Variants

Common pitfalls

Ignoring the fact that 'l' and 'o' appear twice in the word 'balloon'.
Not updating the result if some characters are missing or not sufficient to form a 'balloon'.
Using unnecessary data structures or overly complex approaches when a simple hash table suffices.

Follow-up variants

What if the string contains extra characters not relevant to the word 'balloon'?
What if the input string is much shorter than the word 'balloon'?
How would you approach the problem if it were required to form multiple words instead of just one?

FAQ

How do you solve the 'Maximum Number of Balloons' problem?

Count the frequency of relevant characters ('b', 'a', 'l', 'o', 'n'), then determine how many times you can form 'balloon' based on the minimum count of the required characters.

What is the time complexity of the 'Maximum Number of Balloons' problem?

The time complexity is O(n), where n is the length of the input string, because you need to count the frequency of each character in the string.

What is the primary approach to solving the 'Maximum Number of Balloons' problem?

The primary approach is using a hash table to count character frequencies and then determining the maximum number of times you can form the word 'balloon'.

What are common mistakes in solving the 'Maximum Number of Balloons' problem?

Common mistakes include not accounting for the fact that 'l' and 'o' appear twice, or missing some characters in the frequency count.

How can GhostInterview help me with the 'Maximum Number of Balloons' problem?

GhostInterview provides a structured approach to practicing the key patterns for this problem, helping you master counting techniques and optimize solutions.

terminal

Solution

Solution 1: Counting

We count the frequency of each letter in the string `text`, and then divide the frequency of the letters 'o' and 'l' by 2, because the word `balloon` contains the letters 'o' and 'l' twice.

1

2

3

4

5

6

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        cnt = Counter(text)
        cnt['o'] >>= 1
        cnt['l'] >>= 1
        return min(cnt[c] for c in 'balon')

Continue Practicing

#1160 find words that can be formed by characters #1079 letter tile possibilities #1347 minimum number of steps to make two strings anagram