1189. Maximum Number of Balloons
Problem Description
The problem provides us with a string named text
and expects us to find out how many instances of the word "balloon" can be formed using the characters from text
. Each character in text
can be used only once, therefore it controls how many times the word "balloon" can be assembled. One thing to note is that different characters are needed in different quantities - specifically, 'b', 'a', and 'n' appear once in "balloon", whereas 'l' and 'o' appear twice. The goal is to find the maximum number of complete "balloon" words that can be created without reusing characters.
Intuition
To determine how many times the word "balloon" can be formed, we need to count the occurrences of each character that is required to form the word within text
. Bearing in mind that 'l' and 'o' are needed twice in each instance of "balloon", we must count how many times 'b', 'a', 'l', 'o', and 'n' appear in text
. The approach is straightforward:
- Count the frequency of each character in the input
text
. - Since 'l' and 'o' are required twice, we divide the counted occurrences of 'l' and 'o' by 2. This adjusts their counts to reflect how many full "balloon" instances they can contribute to.
- The number of possible "balloon" instances will then be limited by the character with the least number of usable occurrences after adjustments, as every "balloon" needs at least one of each required character.
- We find the minimum occurrence among the character counts for 'b', 'a', 'l', 'o', and 'n' — this gives us the maximum number of "balloon" instances that can be formed.
Using a Counter
to tally the characters and performing integer division (with the >>
operator which is equivalent to dividing by 2 and flooring the result) on counts of 'l' and 'o' makes the solution efficient and allows us to simply use the min
function to get our answer.
Solution Approach
The implementation of the solution can be understood step by step as follows:
-
Using
Counter
fromcollections
module: Python’sCounter
is a container that stores elements as dictionary keys, and their counts are stored as dictionary values. Instantiating aCounter
object with the stringtext
gives us a dictionary-like object that contains all characters as keys with their respective counts as values. This is beneficial asCounter
efficiently counts the occurrences of each character in the input stringtext
. -
Adjusting counts for 'l' and 'o': Since the word "balloon" contains two 'l' and two 'o' characters, we need to know how many pairs of 'l' and 'o' we have. This is done by right-shifting the count of these characters by 1 position with
cnt['o'] >>= 1
andcnt['l'] >>= 1
. The right shift>>
operator is equivalent to performing integer division by 2 and then flooring the result, which is exactly what we need to get the pair counts for 'l' and 'o'. -
Finding the limiting character count: The
min
function is used to iterate over the counts of 'b', 'a', 'l', 'o', and 'n' in theCounter
object, and to find the smallest count among them. This is because we can only form as many instances of "balloon" as the least common necessary character allows. For example, if we only have one 'b', we cannot form more than one "balloon", regardless of how many 'l's or 'o's we have. -
Returning the result: Finally, the minimum count found is returned which represents the maximum number of times the word "balloon" can be formed from the given
text
.
The algorithm is efficient primarily due to the Counter
data structure, which allows O(n) tallying of characters in text
. Further operations (bitwise shifts and minimum value calculation) are O(1) with respect to the distinct characters involved since the word "balloon" has a constant number of unique characters.
Overall, this implementation is concise and leverages Python's built-in features to solve the problem with minimal lines of code and in efficient time complexity.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's say our input string text
is "loonbalxballpoon".
-
Count characters in
text
:- We instantiate a
Counter
with ourtext
:- Counter will be:
{'l': 3, 'o': 4, 'n': 2, 'b': 2, 'a': 2, 'x': 1, 'p': 1}
- Counter will be:
- In "balloon", 'b' appears 1 time, 'a' appears 1 time, 'l' appears 2 times, 'o' appears 2 times, and 'n' appears 1 time.
- We instantiate a
-
Adjust counts for 'l' and 'o':
- We right-shift the counts for 'l' and 'o' by 1 (integer division by 2):
- After adjustment, 'l' count is 3 >> 1 = 1 and 'o' count is 4 >> 1 = 2 (>> is bit shift to the right which is equivalent to dividing by 2 and flooring the result).
- We right-shift the counts for 'l' and 'o' by 1 (integer division by 2):
-
Find the limiting character count:
- Using the counts we have for 'b', 'a', 'l', 'o', and 'n':
- 'b' count is 2
- 'a' count is 2
- 'l' adjusted count is 1 (from the step above)
- 'o' adjusted count is 2 (from the step above)
- 'n' count is 2
- The character that limits the number of possible "balloon" words is 'l', with an adjusted count of 1.
- Using the counts we have for 'b', 'a', 'l', 'o', and 'n':
-
Final result:
- Since the adjusted 'l' count is 1, we can only form the word "balloon" one time from the input
text
.
- Since the adjusted 'l' count is 1, we can only form the word "balloon" one time from the input
This example helps to illustrate how the use of Counter
, bit shifts, and finding the minimum count among necessary characters enables us to efficiently solve the problem and determine the maximum number of times the word "balloon" can be created from a given string of text.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def maxNumberOfBalloons(self, text: str) -> int:
5 # Create a counter from the characters in the text
6 character_count = Counter(text)
7
8 # The letters 'o' and 'l' appear twice in "balloon", so divide their counts by 2
9 character_count['o'] //= 2
10 character_count['l'] //= 2
11
12 # Return the minimum count among the letters in the word "balloon"
13 # Since 'balloon' has the characters 'b', 'a', 'l' (now halved), 'o' (halved), and 'n'
14 return min(character_count[char] for char in 'balon')
15
1class Solution {
2 public int maxNumberOfBalloons(String text) {
3 // Initialize an array to count the frequency of each character in the given text
4 int[] charFrequency = new int[26];
5
6 // Iterate through each character in the text and increment the count in the array
7 for (int i = 0; i < text.length(); ++i) {
8 ++charFrequency[text.charAt(i) - 'a'];
9 }
10
11 // Since 'l' and 'o' appear twice in "balloon", divide their counts by 2
12 charFrequency['l' - 'a'] >>= 1; // Equivalent to dividing by 2 using bitwise operator
13 charFrequency['o' - 'a'] >>= 1; // Equivalent to dividing by 2 using bitwise operator
14
15 // Initialize the answer with a large number
16 int maxBalloons = Integer.MAX_VALUE;
17
18 // Iterate over the characters of the word "balloon"
19 for (char c : "balon".toCharArray()) {
20 // Find the minimum frequency among the characters 'b', 'a', 'l', 'o', 'n'
21 maxBalloons = Math.min(maxBalloons, charFrequency[c - 'a']);
22 }
23
24 // The minimum frequency determines the maximum number of "balloon" strings that can be formed
25 return maxBalloons;
26 }
27}
28
1#include <algorithm> // For using the std::min function
2#include <string>
3using namespace std;
4
5class Solution {
6public:
7 int maxNumberOfBalloons(string text) {
8 int charCounts[26] = {}; // Initialize an array to store the counts of each letter
9
10 // Count the frequency of each character in the text
11 for (char c : text) {
12 ++charCounts[c - 'a'];
13 }
14
15 // Since 'l' and 'o' are counted twice in "balloon", we need to halve their counts
16 charCounts['o' - 'a'] /= 2;
17 charCounts['l' - 'a'] /= 2;
18
19 // Set the initial answer to a very high value
20 int minBalloons = INT_MAX;
21
22 // "balon" represents the unique characters in "balloon"
23 string balloon = "balon";
24 for (char c : balloon) {
25 // Find the minimum count of the letters in "balon" to determine the answer
26 minBalloons = min(minBalloons, charCounts[c - 'a']);
27 }
28
29 return minBalloons; // Return the minimum number of "balloon" strings
30 }
31};
32
1function maxNumberOfBalloons(text: string): number {
2 // Create an array to keep the count of each letter in the English alphabet initialized with zeroes.
3 const charCount = new Array(26).fill(0);
4
5 // Iterate through the given text and increment the count of each letter.
6 for (const char of text) {
7 charCount[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
8 }
9
10 // Calculate the maximum number of times the word "balloon" can be formed.
11 // For the letters 'l' and 'o', we should divide the count by 2 as they appear twice in the word "balloon".
12 // 'b' is at index 1, 'a' is at index 0, 'l' is at index 11, 'o' is at index 14, and 'n' is at index 13.
13 const maxBalloons = Math.min(
14 charCount['b'.charCodeAt(0) - 'a'.charCodeAt(0)], // Count of 'b'
15 charCount['a'.charCodeAt(0) - 'a'.charCodeAt(0)], // Count of 'a'
16 charCount['l'.charCodeAt(0) - 'a'.charCodeAt(0)] >> 1, // Count of 'l' divided by 2
17 charCount['o'.charCodeAt(0) - 'a'.charCodeAt(0)] >> 1, // Count of 'o' divided by 2
18 charCount['n'.charCodeAt(0) - 'a'.charCodeAt(0)] // Count of 'n'
19 );
20
21 // Return the maximum number of "balloon" strings that can be formed.
22 return maxBalloons;
23}
24
Time and Space Complexity
The time complexity of the code is O(n)
, where n
is the length of the string text
. This is because the code iterates over each character in the string once to construct the Counter
object, which is an operation that takes O(n)
time. After that, the operations that halve the counts for 'o' and 'l' and the minimum finding operation take constant time, since they don't depend on the size of the input string; they only iterate over the fixed set of characters in the string 'balon'.
The space complexity of the code is also O(n)
. Although there are a fixed number of keys ('b', 'a', 'l', 'o', 'n') in the counter that could suggest constant space, in the worst case, the Counter
might store every unique character in the input string if text
does not contain any characters from "balloon". Therefore, the space used by the Counter
object scales with the size of the text
.
Note that these analyses assume typical implementations of Python's Counter
and looping constructs.
Learn more about how to find time and space complexity quickly using problem constraints.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time