Maximum Number of Balloons solution and explanation
Google
9 more videos on this problem
Maximum Number of Balloons - Leetcode 1189 - PythonNeetCode · 7:03 · 28K views
Maximum Number of Balloons - Leetcode 1189 - Hashmaps & Sets (Python)Greg Hogg · 8:21 · 14K views
LeetCode 1189. Maximum Number of Balloons (Solution Explained)Nick White · 7:59 · 8K views
LeetCode 1189: Maximum Number of Balloons - Interview Prep Ep 37Fisher Coder · 8:16 · 3K views
Can You Detect the Word Balloon? (LeetCode 1189: Maximum Number of Balloons)Code With Zi · 6:26 · 2K views
Maximum Number of Balloons | Leetcode 1189 | Live coding session 🔥🔥🔥Coding Decoded · 5:12 · 1K views
Leetcode | 1189. Maximum Number of Balloons | Easy | Java SolutionDeveloper Docs · 4:34 · 1K views
Leetcode 1189.Maximum Number of Balloons.Friendly Neighborhood Coder · 11:27 · 444 views
Maximum Number of Balloons - Leetcode 1189 - C++ - عربيTech Time · 6:28 · 231 views
1189. Maximum Number of Balloons | Leetcode Daily - PythonLeetcode Daily · 4:01 · 229 views
The problem
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 <= 104textconsists of lower case English letters only.
Note: This question is the same as 2287: Rearrange Characters to Make Target String.
Approach overview
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.
Approach 1: Frequency Count Method
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.
from collections import Counter
def maxNumberOfBalloons(text: str) -> int:
count = Counter(text)
count['l'] //= 2
count['o'] //= 2
return min(count[c] for c in 'balon')
print(maxNumberOfBalloons("loonbalxballpoon"))import java.util.HashMap;
import java.util.Map;
public class Solution {
public int maxNumberOfBalloons(String text) {
Map<Character, Integer> count = new HashMap<>();
for (char c : text.toCharArray())
count.put(c, count.getOrDefault(c, 0) + 1);
count.put('l', count.getOrDefault('l', 0) / 2);
count.put('o', count.getOrDefault('o', 0) / 2);
return Math.min(Math.min(Math.min(Math.min(count.getOrDefault('b', 0), count.getOrDefault('a', 0)), count.getOrDefault('l', 0)), count.getOrDefault('o', 0)), count.getOrDefault('n', 0));
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.maxNumberOfBalloons("loonbalxballpoon"));
}
}#include <iostream>
#include <unordered_map>
using namespace std;
int maxNumberOfBalloons(string text) {
unordered_map<char, int> count;
for (char c : text)
count[c]++;
count['l'] /= 2;
count['o'] /= 2;
return min({count['b'], count['a'], count['l'], count['o'], count['n']});
}
int main() {
cout << maxNumberOfBalloons("loonbalxballpoon") << endl;
return 0;
}function maxNumberOfBalloons(text) {
const count = {};
for (const char of text) {
count[char] = (count[char] || 0) + 1;
}
count['l'] = Math.floor((count['l'] || 0) / 2);
count['o'] = Math.floor((count['o'] || 0) / 2);
const minCount = Math.min(count['b'] || 0, count['a'] || 0, count['l'] || 0, count['o'] || 0, count['n'] || 0);
return minCount;
}
console.log(maxNumberOfBalloons("loonbalxballpoon"));#include <stdio.h>
#include <string.h>
int maxNumberOfBalloons(char* text) {
int count[26] = {0};
for (int i = 0; text[i]; i++)
count[text[i] - 'a']++;
count['l' - 'a'] /= 2;
count['o' - 'a'] /= 2;
int min = count['b' - 'a'];
min = min < count['a' - 'a'] ? min : count['a' - 'a'];
min = min < count['l' - 'a'] ? min : count['l' - 'a'];
min = min < count['o' - 'a'] ? min : count['o' - 'a'];
min = min < count['n' - 'a'] ? min : count['n' - 'a'];
return min;
}
int main() {
char text[] = "loonbalxballpoon";
printf("%d\n", maxNumberOfBalloons(text));
return 0;
}using System;
using System.Linq;
public class Solution {
public int MaxNumberOfBalloons(string text) {
var count = new int[26];
foreach (char c in text)
count[c - 'a']++;
count['l' - 'a'] /= 2;
count['o' - 'a'] /= 2;
return new [] {count['b' - 'a'], count['a' - 'a'], count['l' - 'a'], count['o' - 'a'], count['n' - 'a']}.Min();
}
public static void Main() {
var solution = new Solution();
Console.WriteLine(solution.MaxNumberOfBalloons("loonbalxballpoon"));
}
}The Python solution uses the Counter class to count character frequencies. After adjusting counts for 'l' and 'o', it finds the minimum frequency among the required characters to determine the number of 'balloon' instances.
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), since the space usage is limited to the 26 lowercase letters.
Approach 2: Character Frequency Ratio Method
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.
def maxNumberOfBalloons(text: str) -> int:
b, a, l, o, n = 0, 0, 0, 0, 0
for c in text:
if c == 'b': b += 1
elif c == 'a': a += 1
elif c == 'l': l += 1
elif c == 'o': o += 1
elif c == 'n': n += 1
l //= 2
o //= 2
return min(b, a, l, o, n)
print(maxNumberOfBalloons("loonbalxballpoon"))public class Solution {
public int maxNumberOfBalloons(String text) {
int[] count = new int[5]; // b, a, l, o, n
for (char c : text.toCharArray()) {
if (c == 'b') count[0]++;
else if (c == 'a') count[1]++;
else if (c == 'l') count[2]++;
else if (c == 'o') count[3]++;
else if (c == 'n') count[4]++;
}
count[2] /= 2;
count[3] /= 2;
return Math.min(Math.min(Math.min(Math.min(count[0], count[1]), count[2]), count[3]), count[4]);
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.maxNumberOfBalloons("loonbalxballpoon"));
}
}#include <iostream>
#include <unordered_map>
using namespace std;
int maxNumberOfBalloons(string text) {
int count[5] = {0}; // b, a, l, o, n
for (char c : text) {
if (c == 'b') count[0]++;
else if (c == 'a') count[1]++;
else if (c == 'l') count[2]++;
else if (c == 'o') count[3]++;
else if (c == 'n') count[4]++;
}
count[2] /= 2;
count[3] /= 2;
return min({count[0], count[1], count[2], count[3], count[4]});
}
int main() {
cout << maxNumberOfBalloons("loonbalxballpoon") << endl;
return 0;
}function maxNumberOfBalloons(text) {
let b = 0, a = 0, l = 0, o = 0, n = 0;
for (let c of text) {
if (c === 'b') b++;
else if (c === 'a') a++;
else if (c === 'l') l++;
else if (c === 'o') o++;
else if (c === 'n') n++;
}
l = Math.floor(l / 2);
o = Math.floor(o / 2);
return Math.min(b, a, l, o, n);
}
console.log(maxNumberOfBalloons("loonbalxballpoon"));#include <stdio.h>
#include <string.h>
int maxNumberOfBalloons(char* text) {
int b = 0, a = 0, l = 0, o = 0, n = 0;
for (int i = 0; text[i]; i++) {
if (text[i] == 'b') b++;
else if (text[i] == 'a') a++;
else if (text[i] == 'l') l++;
else if (text[i] == 'o') o++;
else if (text[i] == 'n') n++;
}
l /= 2;
o /= 2;
return b < a ? (b < l ? (b < o ? (b < n ? b : n) : (o < n ? o : n)) : (l < o ? (l < n ? l : n) : (o < n ? o : n))) :
(a < l ? (a < o ? (a < n ? a : n) : (o < n ? o : n)) : (l < o ? (l < n ? l : n) : (o < n ? o : n)));
}
int main() {
char text[] = "loonbalxballpoon";
printf("%d\n", maxNumberOfBalloons(text));
return 0;
}using System;
public class Solution {
public int MaxNumberOfBalloons(string text) {
int b = 0, a = 0, l = 0, o = 0, n = 0;
foreach (char c in text) {
if (c == 'b') b++;
else if (c == 'a') a++;
else if (c == 'l') l++;
else if (c == 'o') o++;
else if (c == 'n') n++;
}
l /= 2;
o /= 2;
return Math.Min(b, Math.Min(a, Math.Min(l, Math.Min(o, n))));
}
public static void Main() {
Solution solution = new Solution();
Console.WriteLine(solution.MaxNumberOfBalloons("loonbalxballpoon"));
}
}The Python solution uses individual variables to maintain character counts for 'b', 'a', 'l', 'o', and 'n'. It divides the 'l' and 'o' counts by 2 to adjust double usage and then calculates the minimum possible count of full 'balloon' sets.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), given a constant number of variables are used.
Approach 3: 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.
function maxNumberOfBalloons(text: string): number {
const cnt = new Array(26).fill(0);
for (const c of text) {
cnt[c.charCodeAt(0) - 97]++;
}
return Math.min(cnt[0], cnt[1], cnt[11] >> 1, cnt[14] >> 1, cnt[13]);
}func maxNumberOfBalloons(text string) int {
cnt := [26]int{}
for _, c := range text {
cnt[c-'a']++
}
cnt['l'-'a'] >>= 1
cnt['o'-'a'] >>= 1
ans := 1 << 30
for _, c := range "balon" {
if x := cnt[c-'a']; ans > x {
ans = x
}
}
return ans
}impl Solution {
pub fn max_number_of_balloons(text: String) -> i32 {
let mut arr = [0; 5];
for c in text.chars() {
match c {
'b' => {
arr[0] += 1;
}
'a' => {
arr[1] += 1;
}
'l' => {
arr[2] += 1;
}
'o' => {
arr[3] += 1;
}
'n' => {
arr[4] += 1;
}
_ => {}
}
}
arr[2] /= 2;
arr[3] /= 2;
let mut res = i32::MAX;
for num in arr {
res = res.min(num);
}
res
}
}class Solution {
/**
* @param String $text
* @return Integer
*/
function maxNumberOfBalloons($text) {
$cnt1 = $cnt2 = $cnt3 = $cnt4 = $cnt5 = 0;
for ($i = 0; $i < strlen($text); $i++) {
if ($text[$i] == 'b') {
$cnt1 += 1;
} elseif ($text[$i] == 'a') {
$cnt2 += 1;
} elseif ($text[$i] == 'l') {
$cnt3 += 1;
} elseif ($text[$i] == 'o') {
$cnt4 += 1;
} elseif ($text[$i] == 'n') {
$cnt5 += 1;
}
}
$cnt3 = floor($cnt3 / 2);
$cnt4 = floor($cnt4 / 2);
return min($cnt1, $cnt2, $cnt3, $cnt4, $cnt5);
}
}Complexity comparison
| 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 string. |
| Counting | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Maximum Number of Balloons easy or hard?
Maximum Number of Balloons is classified as an Easy problem on LeetCode with a moderate acceptance rate around 60%. The difficulty comes from recognizing that some characters in "balloon" appear twice, which requires dividing their counts when calculating the final answer.
How to solve Maximum Number of Balloons in O(n)?
Iterate through the string and count the frequency of each character using an array or hash map. After counting, compute the number of possible "balloon" words by evaluating b, a, l/2, o/2, and n. The smallest of these values is the result. This requires one pass through the string and constant extra memory.
What is the best approach for Maximum Number of Balloons?
The best approach uses character frequency counting. Count how many times each letter appears in the string, then determine how many "balloon" words can be formed by checking the required counts of b, a, l, o, and n. Since l and o appear twice, divide their counts by two. The minimum value among these determines the answer in O(n) time and O(1) space.
Is Maximum Number of Balloons asked at Google/Amazon/Meta?
This problem represents a common string frequency counting pattern frequently used in technical interviews at large tech companies. Variations of character counting and resource allocation problems appear in interviews at companies like Amazon, Google, and Meta when evaluating hash table and string manipulation skills.
What data structure is used in Maximum Number of Balloons?
The primary data structure is a hash table or a fixed-size frequency array. It stores how many times each character appears in the string. Because the input consists of lowercase English letters, many solutions use an integer array of size 26 for constant-time updates and lookups.
What is the time complexity of Maximum Number of Balloons?
The optimal solution runs in O(n) time where n is the length of the input string. The algorithm scans the string once to build character frequencies and then performs a constant number of checks for the letters in "balloon". Space complexity is O(1) because the frequency array size is fixed at 26 letters.
Maximum Number of Balloons Python or Java solution approach?
Both Python and Java implementations follow the same idea: count character frequencies and compute the limiting character among b, a, l/2, o/2, and n. Python often uses collections.Counter, while Java typically uses an int[26] array. Both implementations achieve O(n) time and O(1) space complexity.