Maximum Number of Balloons - Video Solutions
Maximum Number of Balloons - Leetcode 1189 - Python
Maximum Number of Balloons - Video Solution
Watch 10 video solutions for Maximum Number of Balloons, a easy level problem involving Hash Table, String, Counting. This walkthrough by NeetCode has 28,854 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
Example 1:
Input: text = "nlaebolko" Output: 1
Example 2:
Input: text = "loonbalxballpoon" Output: 2
Example 3:
Input: text = "leetcode" Output: 0
Constraints:
1 <= text.length <= 104textconsists of lower case English letters only.
Note: This question is the same as 2287: Rearrange Characters to Make Target String.
Approach Overview
Problem Overview: Given a string text, determine how many times you can form the word "balloon" using the characters in the string. Each character in text can be used only once per instance of the word.
Approach 1: Frequency Count Method (O(n) time, O(1) space)
Count how many times each character appears in the input string. A simple array of size 26 or a hash map works well for this hash table counting pattern. After building the frequency map, check how many complete "balloon" words can be formed. The word requires b=1, a=1, l=2, o=2, and n=1. Divide the counts of l and o by 2 since they appear twice in the target word. The smallest resulting value across these characters determines the maximum number of balloons you can build.
This approach scans the string once, performs constant-time updates, and then checks a fixed set of characters. Time complexity is O(n), and space complexity is O(1) because the alphabet size is constant. This pattern appears frequently in string counting problems.
Approach 2: Character Frequency Ratio Method (O(n) time, O(1) space)
This method treats the problem as a ratio comparison between the characters in text and the required characters of the word "balloon". First compute the frequency of characters in the input string using a counting array. Then compute the ratio count[c] / required[c] for each character needed in the target word. For example, if text contains 6 l characters and the word requires 2, that contributes 6 / 2 = 3 possible uses.
The answer is the minimum ratio among all required characters. This guarantees that every instance of "balloon" has enough letters available. Like the previous method, the algorithm processes the string once and performs constant work afterward. Time complexity remains O(n), and space complexity stays O(1). Conceptually this frames the problem as a constrained resource allocation problem based on counting.
Recommended for interviews: The frequency count approach is what most interviewers expect. It demonstrates that you recognize a character counting pattern and can translate the requirements of the target word into frequency constraints. The ratio interpretation is equally efficient but mainly reframes the same idea mathematically. Showing the counting solution first proves you understand the core pattern used in many string and hash table interview problems.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Count Method | O(n) | O(1) | General solution for string character counting problems |
| Character Frequency Ratio Method | O(n) | O(1) | When modeling the problem as resource ratios between available and required characters |