Back to solutions

Maximum Number of Balloons

EasyArrays

How many times can the word 'balloon' be formed from the letters?

Open problem
Constraints
  • 1 <= length <= 10^4
  • Lowercase English letters

Count limiting letters

Time O(n)Space O(1)

The word 'balloon' needs b, a, l, l, o, o, n. Count every letter in the text, then halve the counts for l and o (each is needed twice). The number of words you can build is the minimum of those five available amounts.

Key terms
frequency count:
How many times each character appears in the text.
bottleneck:
The scarcest required letter, which caps how many words you can form.
int maxNumberOfBalloons(const string& text) {
    int cnt[26] = {0};
    for (char c : text) cnt[c - 'a']++;
    return min({cnt['b'-'a'], cnt['a'-'a'], cnt['l'-'a']/2, cnt['o'-'a']/2, cnt['n'-'a']});
}
Step by step
  1. Count occurrences of each letter in the text.
  2. Compute available b, a, n directly and l, o divided by two (needed twice each).
  3. The answer is the minimum of b, a, l/2, o/2, n the limiting letter.