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 <= 104text consists of lower case English letters only.
Note: This question is the same as 2287: Rearrange Characters to Make Target String.
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.
This approach involves counting the frequency of each character in the string 'text' and then determining how many full instances of the word 'balloon' can be formed based on these frequencies. We will count the occurrences of the characters 'b', 'a', 'l', 'o', and 'n'. Since 'l' and 'o' appear twice in the word 'balloon', their counts should be halved. Finally, we find the minimum number of complete 'balloon' words that can be formed using these character counts.
The C solution uses an array of size 26 to store the frequency of each letter in the input string 'text'. The count for 'l' and 'o' is divided by two because they appear twice in 'balloon'. Finally, it calculates the minimum count required among 'b', 'a', 'l', 'o', and 'n' to determine how many instances of 'balloon' can be formed.
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), since we are using a constant amount of extra space.
Instead of counting characters explicitly, this approach calculates the maximum number of 'balloon' instances by directly comparing the ratios of character counts required. Specifically, for 'b', 'a', and 'n', the ratio is 1:1, but for 'l' and 'o', the ratio is 1:2 in 'balloon'. This approach simplifies checking character sufficiency by calculating the feasible number of 'balloon' words based on the complete sets of these character combinations.
This C solution defines separate counts for each character directly required to form 'balloon'. It then computes how many full 'balloon' sets can be constructed based on these adjusted character counts, particularly halving the 'l' and 'o' counts.
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), as it uses a fixed number of variables for 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.
Next, we traverse each letter in the word balon, and find the minimum frequency of each letter in the string text. This minimum frequency is the maximum number of times the word balloon can appear in the string text.
The time complexity is O(n), and the space complexity is O(C). Here, n is the length of the string text, and C is the size of the character set. In this problem, C = 26.
| Approach | Complexity |
|---|---|
| Frequency Count Method | Time Complexity: O(n), where n is the length of the input string. |
| Character Frequency Ratio Method | Time Complexity: O(n), where n is the length of the input string. |
| Counting | — |
| 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 |
Maximum Number of Balloons - Leetcode 1189 - Python • NeetCode • 27,689 views views
Watch 9 more video solutions →Practice Maximum Number of Balloons with our built-in code editor and test cases.
Practice on FleetCode