1189. Maximum Number of Balloons

Time: O(n)

Space: O(1)

Problem Overview

Each "balloon" uses one b, one a, one n, and two each of l and o.

Intuition

Each "balloon" uses one b, one a, one n, and two each of l and o. Count every letter in text, then see how many complete words you can form. The bottleneck is whichever required letter runs out first — l and o each contribute count/2 because two are needed per word.

Algorithm

1Count frequency of each lowercase letter in text.
2Initialize ans to a large value.
3For b, a, n: ans = min(ans, count[letter]).
4For o and l: ans = min(ans, count[letter] / 2).
5Return ans.

Example Walkthrough

Input: text = "nlaebolko"

1.Counts: b=1, a=1, l=2, o=2, n=1 (and extras).
2.b, a, n each allow 1 word.
3.l: 2/2 = 1, o: 2/2 = 1.
4.Minimum quota = 1 → one "balloon".

Output: 1

Common Pitfalls

•l and o need integer division by 2 — two per balloon.
•Do not forget n — it is easy to only check b, a, l, o.
•Initialize ans with int.MaxValue before taking mins.

1189.cs

// Approach: Count letter frequencies. "balloon" needs b, a, n once each and l, o twice each.
// Answer is the minimum of those quotas: count/2 for l and o, raw count for b, a, n.
// Time: O(n) Space: O(1)
public class Solution
{
    public int MaxNumberOfBalloons(string text)
    {
        int ans = int.MaxValue;
        int[] count = new int[26];

        foreach (char c in text)
            count[c - 'a']++;

        foreach (char c in new char[] { 'b', 'a', 'n' })
            ans = Math.Min(ans, count[c - 'a']);

        foreach (char c in new char[] { 'o', 'l' })
            ans = Math.Min(ans, count[c - 'a'] / 2);

        return ans;
    }
}

Was this solution helpful?