Maximum Number of Balloons
Problem Description
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 <= 104
textconsists of lower case English letters only.
Solve it on LeetCode
Approaches
1. Frequency Count with Maps
Intuition:
- The word "balloon" consists of the letters: 'b', 'a', 'l', 'o', 'n'.
- We need to count these letters in the input string and determine how many times we can form the word "balloon".
- For 'l' and 'o', we need the count divided by 2 because these letters appear twice in "balloon".
Steps:
- Create a frequency map for the characters in the input string.
- Check the count of each character needed for "balloon".
- The count of possible "balloons" that can be formed is determined by the minimum ratio of available to needed instances of these characters.
Code:
- Time Complexity: O(n), where n is the length of the input string; we traverse the string to build the frequency map.
- Space Complexity: O(1), since the frequency map only contains a fixed number of characters (at most the size of the alphabet).
2. Optimized Frequency Count with Arrays
Intuition:
This approach builds on the idea of counting character frequencies, but instead of using a map or dictionary, which carries extra overhead, we use a fixed-size array of length 26.
Since the problem only involves lowercase English letters, each character 'a' to 'z' can be mapped directly to an array index (c - 'a'), making both counting and lookups extremely fast.
Once we know how many times each required character appears in the input string, we compute how many full occurrences of the word "balloon" can be formed.
Steps:
- Create an integer array of size 26 to store the frequency of each lowercase letter.
- Count the characters in the input string by incrementing the corresponding index in the array.
- For each character in the word
"balloon"(b,a,l,l,o,o,n), compute how many times it can contribute to forming the word. - For
'l'and'o', divide counts by 2 because each appears twice. - The answer is the minimum among these available counts.
Code:
- Time Complexity: O(n), where n is the length of the input string; similar to approach 1 but simplified.
- Space Complexity: O(1), as we use a fixed-size array independent of the input size.
Example Walkthrough:
Imagine counting characters in "loonbalxballpoon":
To form "balloon":
The limiting character is 'a', so the maximum balloons = 1.