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.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
Maximum Number of Balloons - Leetcode 1189 - Python • NeetCode • 25,417 views views
Watch 9 more video solutions →Practice Maximum Number of Balloons with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor