Maximum Number of Balloons — Solution in Python, Java & C++
Maximum Number of Balloons solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Maximum Number of Balloons is an easy coding problem on strings, hash table and counting, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Strings, Hash Table, Counting
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string text, use its characters to spell as many copies of the word "balloon" as possible. Each character of text may be used at most once.
Return the maximum number of copies you can spell.
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 <= 40text consists of lowercase English letters.
Hints for Maximum Number of Balloons
Hint 1
Only five letters matter: b, a, l, o, n — and "balloon" needs two each of l and o.
Hint 2
Divide each available count by how many that letter is needed, rounding down.
Hint 3
The answer is the smallest of those five quotients — the scarcest letter is the bottleneck.
How to solve Maximum Number of Balloons
Each copy needs one b, one a, two ls, two os and one n; the scarcest letter after dividing by its requirement is the bottleneck.
Approach
- Count the characters of
text. - For each of
b:1, a:1, l:2, o:2, n:1, computecount // need. - Return the minimum.
Why it works
The number of complete words is limited by whichever letter runs out first, and count // need is how many words that letter alone could supply.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Forgetting that
landoare needed twice doubles the answer.
Reference solution
Python
def maxNumberOfBalloons(text: str) -> int:
count = {}
for ch in text:
count[ch] = count.get(ch, 0) + 1
need = [("b", 1), ("a", 1), ("l", 2), ("o", 2), ("n", 1)]
return min(count.get(ch, 0) // k for ch, k in need)Java
public static int maxNumberOfBalloons(String text) {
int[] count = new int[26];
for (int i = 0; i < text.length(); i++) count[text.charAt(i) - 'a']++;
int[] idx = {'b' - 'a', 'a' - 'a', 'l' - 'a', 'o' - 'a', 'n' - 'a'};
int[] needed = {1, 1, 2, 2, 1};
int best = Integer.MAX_VALUE;
for (int i = 0; i < 5; i++) {
best = Math.min(best, count[idx[i]] / needed[i]);
}
return best;
}C++
int maxNumberOfBalloons(string text) {
int count[26] = {0};
for (char c : text) count[c - 'a']++;
int idx[5] = {'b' - 'a', 'a' - 'a', 'l' - 'a', 'o' - 'a', 'n' - 'a'};
int needed[5] = {1, 1, 2, 2, 1};
int best = count[idx[0]] / needed[0];
for (int i = 1; i < 5; i++) {
int copies = count[idx[i]] / needed[i];
if (copies < best) best = copies;
}
return best;
}JavaScript
var maxNumberOfBalloons = function(text) {
const count = {};
for (let i = 0; i < text.length; i++) {
count[text[i]] = (count[text[i]] || 0) + 1;
}
const need = [["b", 1], ["a", 1], ["l", 2], ["o", 2], ["n", 1]];
let best = Infinity;
for (let i = 0; i < need.length; i++) {
const have = count[need[i][0]] || 0;
const copies = Math.floor(have / need[i][1]);
if (copies < best) best = copies;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets