Hash MapsEasyO(n) time · O(1) space

Maximum Number of Balloons

Ramayana — Sita's Festival — How Many Times Can We Spell 'BALLOON'?

एकं शब्दं रचयितुं — कति वर्णाः पर्याप्ताः?। न्यूनतमः गणनां जानीहि — उत्तरं तत्रैव॥

*To form one word — how many letters are sufficient? Know the minimum count — the answer lies there.*

The Story

Given a string `text`, return the maximum number of times we can spell the word "balloon" using the characters in `text`.

For `text = "nlaebolko"`, answer = 1. For `text = "loonbalxballpoon"`, answer = 2.

Sita was decorating the palace for Diwali. She had a bag of letter tiles. She wanted to know the maximum number of "balloon" banners she could spell.

**Key insight:** "balloon" = b(1), a(1), l(2), o(2), n(1) - 'l' appears 2 times in "balloon" → usable count = freq['l'] / 2 - 'o' appears 2 times in "balloon" → usable count = freq['o'] / 2 - b, a, n appear once → usable count = freq directly

Answer = min of all usable counts.

```java int[] f = new int[26]; for (char c : text.toCharArray()) f[c-'a']++; return Math.min(f['b'-'a'], Math.min(f['a'-'a'], Math.min(f['l'-'a']/2, Math.min(f['o'-'a']/2, f['n'-'a'])))); ```

Trace `"loonbalxballpoon"`: Counts: b=2, a=2, l=4, o=4, n=2, (x=1 ignored) Usable: b=2, a=2, l=4/2=2, o=4/2=2, n=2 Min = 2 ✓

"The bottleneck letter determines the answer," Sita realized. "We can only make as many 'balloon's as the most constrained letter allows. Divide-by-two for letters that appear twice in the word."

The One-by-One Speller

Repeatedly try to spell "balloon" from available characters, decrementing counts. Count how many times until we run out. O(n) — same as optimal but less elegant.

java

public int maxNumberOfBalloonsBruteForce(String text) {
    int[] freq = new int[26];
    for (char c : text.toCharArray()) freq[c-'a']++;
    int count = 0;
    while (freq['b'-'a']>=1 && freq['a'-'a']>=1 && freq['l'-'a']>=2
           && freq['o'-'a']>=2 && freq['n'-'a']>=1) {
        freq['b'-'a']--; freq['a'-'a']--;
        freq['l'-'a']-=2; freq['o'-'a']-=2; freq['n'-'a']--;
        count++;
    }
    return count;
}

Sita's Minimum-Count Wisdom

Count frequencies. For letters appearing twice in 'balloon' (l, o): divide by 2. Answer = min across all 5 required letter counts. O(1) space — only track 5 letters.

java

public int maxNumberOfBalloons(String text) {
    int[] f = new int[26];
    for (char c : text.toCharArray()) f[c-'a']++;
    return Math.min(f['b'-'a'],
           Math.min(f['a'-'a'],
           Math.min(f['l'-'a']/2,
           Math.min(f['o'-'a']/2, f['n'-'a']))));
}

Step-by-Step Walkthrough

text="balon" (1 of each)
f: b=1,a=1,l=1,o=1,n=1
Usable: b=1,a=1,l=0 (1/2=0!),o=0,n=1
min=0 ✅ (not enough l's and o's for even one "balloon")

Deep Insight

**Generalization:** For any target word, count each character's required frequency in the word. For each character in text, divide text-count by required-count. Minimum over all = answer.

**Why integer division (floor) works:** If we need 2 l's per balloon and have 5 l's: 5/2=2 complete pairs (one l is wasted). Floor division correctly handles this.

**O(1) space** because we only need 5 character counts for 'balloon'. If the target word had more distinct characters, the space would be proportional to those distinct characters — still O(1) for a fixed target word.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n)	O(1)	Count then loop to decrement
Optimal	O(n)	O(1)	Single pass count, one min computation

Pattern Recognition

✅ How many times can we form target word from text
✅ Count frequency; divide by target word's requirement
✅ Answer = minimum across all required character ratios
✅ O(1) space for fixed target

**LeetCode Trigger Phrases:**
→ "maximum number of balloons"
→ "how many times can you form word X"
→ Character frequency with variable requirements per char

Bhagavad Gita 3.13

यज्ञशिष्टाशिनः सन्तो मुच्यन्ते सर्वकिल्बिषैः। भुञ्जते ते त्वघं पापा ये पचन्त्यात्मकारणात्॥

The devotees of the Lord are released from all kinds of sins because they eat food which is offered first for sacrifice. Others, who prepare food for their own sake, eat only sin.

Connection: Sita distributes the festival letters like prasad — first ensuring every 'balloon' word is complete before counting the surplus. The minimum count is the principle of fair distribution: no word is formed unless all its required letters are present. The algorithm embodies this completeness — it never tries to form an incomplete word. The bottleneck letter teaches that abundance in some areas cannot compensate for scarcity in another.