Maximum Number of Balloons

Easy
236.

Maximum Number of Balloons

Maximum Number of Balloons is an easy coding problem on strings, hash table and counting, asked in Amazon and Adobe interviews.

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 <= 40
  • text consists of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} text
 * @return {number}
 */
var maxNumberOfBalloons = function(text) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 40
  • text consists of lowercase English letters.

Hints for Maximum Number of Balloons

  1. Hint 1

    Only five letters matter: b, a, l, o, n — and "balloon" needs two each of l and o.

  2. Hint 2

    Divide each available count by how many that letter is needed, rounding down.

  3. 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

  1. Count the characters of text.
  2. For each of b:1, a:1, l:2, o:2, n:1, compute count // need.
  3. 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 l and o are 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