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.
In #1189 Maximum Number of Balloons, the goal is to determine how many times the word "balloon" can be formed using the characters of a given string. Since each character can only be used once per formation, the key idea is to analyze the frequency of required characters.
A common approach is to use a hash table or frequency array to count how many times each character appears in the input string. Then compare these counts with the characters needed to form the target word. Some characters appear more than once in "balloon" (such as l and o), so their counts must be handled carefully when determining the limiting factor.
The final answer is determined by identifying the minimum possible formations based on these character frequencies. This approach processes the string once, resulting in O(n) time complexity with O(1) extra space when using a fixed-size character map.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map / Frequency Counting | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Count the frequency of letters in the given string.
Find the letter than can make the minimum number of instances of the word "balloon".
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.
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.
1#include <stdio.h>
2#include <string.h>
3
4int maxNumberOfBalloons(char* text) {
5 int count[26] =
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.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of string frequency and counting problems are commonly asked in technical interviews at companies like Google, Amazon, and Meta. This problem helps test understanding of hash tables, string manipulation, and counting techniques.
A hash table or a frequency array of size 26 works best for this problem. These structures allow efficient counting of characters and constant-time lookups when checking required frequencies.
The optimal approach is to count the frequency of characters using a hash table or fixed-size array. Then compare these counts with the required letters in the word "balloon". The minimum possible formation based on these counts gives the final result.
The word "balloon" contains two 'l' characters and two 'o' characters. Because of this, their frequency in the input string must be divided appropriately when calculating how many complete words can be formed.
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.