Maximum Number of Balloons

easy hash table string counting

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.

Inputtext = "loonbalxballpoon"

Output2

The letters allow exactly two copies of "balloon"; both 'l' and 'o' are needed twice per word.

text (letters only)

def max_number_of_balloons(text):
    counts = {}
    for ch in text:
        counts[ch] = counts.get(ch, 0) + 1
    need = {"b": 1, "a": 1, "l": 2, "o": 2, "n": 1}
    best = float("inf")
    for ch, k in need.items():
        best = min(best, counts.get(ch, 0) // k)
    return best

function maxNumberOfBalloons(text) {
  const counts = {};
  for (const ch of text) counts[ch] = (counts[ch] || 0) + 1;
  const need = { b: 1, a: 1, l: 2, o: 2, n: 1 };
  let best = Infinity;
  for (const ch in need) {
    best = Math.min(best, Math.floor((counts[ch] || 0) / need[ch]));
  }
  return best;
}

class Solution {
    public int maxNumberOfBalloons(String text) {
        int[] counts = new int[26];
        for (char ch : text.toCharArray()) counts[ch - 'a']++;
        int best = Integer.MAX_VALUE;
        best = Math.min(best, counts['b' - 'a']);
        best = Math.min(best, counts['a' - 'a']);
        best = Math.min(best, counts['l' - 'a'] / 2);
        best = Math.min(best, counts['o' - 'a'] / 2);
        best = Math.min(best, counts['n' - 'a']);
        return best;
    }
}

int maxNumberOfBalloons(string text) {
    int counts[26] = {0};
    for (char ch : text) counts[ch - 'a']++;
    int best = INT_MAX;
    best = min(best, counts['b' - 'a']);
    best = min(best, counts['a' - 'a']);
    best = min(best, counts['l' - 'a'] / 2);
    best = min(best, counts['o' - 'a'] / 2);
    best = min(best, counts['n' - 'a']);
    return best;
}

Explanation

To spell "balloon" you need specific letters in specific amounts: one each of b, a, n, but two of l and two of o. The number of full words you can build is capped by whichever required letter runs out first.

So we count how often each letter appears in the text, then for each needed letter compute how many words it alone could support: have // need. For l and o we divide by 2 because each word eats two of them.

The answer is the minimum of those per-letter limits — the scarcest letter is the bottleneck. We take min across b, a, l/2, o/2, n.

Example: text = "loonbalxballpoon". Counts give b:2, a:2, l:4, o:4, n:2. Per-letter limits are 2, 2, 4÷2=2, 4÷2=2, 2 — all 2, so we can make 2 copies of "balloon".

Integer division naturally throws away leftovers (an odd extra l can't help), and any letter not in the text counts as 0, immediately capping the answer at 0.

Time: O(n) Space: O(1)