Maximum Number of Balloons
Easy · Arrays & Hashing · Hash Table · String · Counting
Problem
You are given a string text. You want to cut letters out of it to spell the word "balloon" as many times as possible, using each character of text at most once.
Return the largest number of complete copies of "balloon" you can form.
Examples
Input: text = "loonbalxballoon" Output: 2
There are 2 b, 2 a, 4 l, 4 o and 2 n: enough for two copies.
Input: text = "balon" Output: 0
Each copy needs two l and two o, and there is only one of each.
Input: text = "lloonbablloo" Output: 1
There are 4 l and 4 o, but only one b, one a and one n.
Constraints
- 1 <= len(text) <= 10^4
- text consists of lowercase English letters only
Approaches
- Spell copies one at a time — time O(n · copies), space O(n)
Follow-up
What if the word were an input? Count the word too, and take the minimum of have[c] // need[c] over its letters (see the first use case). And if you could add letters, the question becomes how many to add for k copies (the second use case).
Related problems
Start free on Cariara · Coding problems · System design studio
