LogoKode$word

LeetCode 1189: Maximum Number of Balloons – Java HashMap and Frequency Counting Solution

SEO Subtitle Learn Multiple Approaches, Frequency Analysis, Dry Run, Complexity Breakdown, and Interview Insights for This Popular String Counting Problem

Krishna Shrivastava
2 views
LinkedInGithubX
0
0
LeetcodeEasyJavaHashMapFrequency Count
LeetCode 1189: Maximum Number of Balloons – Java HashMap and Frequency Counting Solution
Listen to articleAudio version
Ad

Introduction

LeetCode 1189, Maximum Number of Balloons, is a beginner-friendly string and frequency-counting problem that teaches an important interview concept:

Count only the characters that matter and determine the limiting factor.

The challenge is to find how many times the word "balloon" can be formed using the characters available in a given string. Each character can be used at most once.

This problem is an excellent introduction to:

  1. HashMap frequency counting
  2. Character frequency analysis
  3. Greedy counting techniques
  4. Finding bottleneck characters

Problem Statement

Problem Link -: Maximum Number of Balloons

Given a string:

text

Determine the maximum number of times the word:

balloon

can be formed.

Each character from the original string can only be used once.

Return the maximum number of complete instances of the word.

Example 1

Input

text = "nlaebolko"

Output

1

Explanation

Available characters:

b = 1
a = 1
l = 2
o = 2
n = 1

Exactly one "balloon" can be formed.

Example 2

Input

text = "loonbalxballpoon"

Output

2

Explanation

The string contains enough characters to create:

balloon
balloon

Two complete words can be formed.

Example 3

Input

text = "leetcode"

Output

0

Explanation

The required characters for "balloon" are not all present.

Key Observation

The target word is:

balloon

Character requirements:

CharacterRequired Count
b1
a1
l2
o2
n1

Notice:

l appears twice
o appears twice

These characters become important because they require more occurrences than the others.

Approach 1: Simulate Building Balloons

Idea

  1. Count occurrences of relevant characters.
  2. Continuously check whether a complete "balloon" can be formed.
  3. If possible:
  4. Increment answer.
  5. Remove required characters.
  6. Repeat until impossible.

Java Solution

class Solution {
public int maxNumberOfBalloons(String text) {

HashMap<Character, Integer> mp = new HashMap<>();

for (int i = 0; i < text.length(); i++) {

if (text.charAt(i) == 'b' ||
text.charAt(i) == 'a' ||
text.charAt(i) == 'l' ||
text.charAt(i) == 'o' ||
text.charAt(i) == 'n') {

mp.put(text.charAt(i),
mp.getOrDefault(text.charAt(i), 0) + 1);
}
}

int ans = 0;

for (int i = 0; i < text.length(); i++) {

if (mp.containsKey('b') &&
mp.containsKey('a') &&
mp.containsKey('l') &&
mp.containsKey('o') &&
mp.containsKey('n')) {

if (mp.get('b') > 0 &&
mp.get('a') > 0 &&
mp.get('l') >= 2 &&
mp.get('o') >= 2 &&
mp.get('n') > 0) {

ans++;

mp.put('b', mp.get('b') - 1);
mp.put('a', mp.get('a') - 1);
mp.put('l', mp.get('l') - 2);
mp.put('o', mp.get('o') - 2);
mp.put('n', mp.get('n') - 1);
}
}
}

return ans;
}
}

Dry Run

Input

text = "loonbalxballpoon"

Frequency Count

b = 2
a = 2
l = 4
o = 4
n = 2

First Balloon

Consume:

b = 1
a = 1
l = 2
o = 2
n = 1

Answer:

1

Second Balloon

Consume again:

b = 0
a = 0
l = 0
o = 0
n = 0

Answer:

2

No more balloons can be formed.

Final result:

2

Can We Optimize Further?

Yes.

Your solution repeatedly removes characters to form balloons.

But we don't actually need simulation.

Instead, we can directly calculate the maximum number of balloons.

Approach 2: Frequency Division (Optimal)

Key Insight

Suppose frequencies are:

b = 5
a = 3
l = 8
o = 4
n = 2

Since:

balloon = b×1
a×1
l×2
o×2
n×1

Possible balloons:

b → 5
a → 3
l → 8/2 = 4
o → 4/2 = 2
n → 2

The smallest value determines the answer:

min(5,3,4,2,2) = 2

Therefore:

answer =
min(
freq['b'],
freq['a'],
freq['l']/2,
freq['o']/2,
freq['n']
)

Optimized Java Solution

class Solution {

public int maxNumberOfBalloons(String text) {

int[] freq = new int[26];

for (char ch : text.toCharArray()) {
freq[ch - 'a']++;
}

return Math.min(
Math.min(freq['b' - 'a'], freq['a' - 'a']),
Math.min(
freq['l' - 'a'] / 2,
Math.min(
freq['o' - 'a'] / 2,
freq['n' - 'a']
)
)
);
}
}

Approach 3: HashMap + Minimum Formula

If you prefer HashMaps:

HashMap<Character,Integer> map = new HashMap<>();

Count frequencies and apply the same minimum formula.

This keeps the logic intuitive while avoiding repeated simulation.

Complexity Analysis

Simulation Approach

Time Complexity

O(n)

The second loop runs at most n times.

Space Complexity

O(1)

Only a few characters are stored.

Optimal Frequency Division Approach

Time Complexity

O(n)

Single traversal.

Space Complexity

O(1)

Fixed-size frequency array.

Interview Discussion

An interviewer may ask:

Why divide l and o by 2?

Because the word contains:

balloon

and requires:

2 l's
2 o's

for every single occurrence.

Therefore:

available balloons from l = lCount / 2

available balloons from o = oCount / 2

Common Mistakes

Forgetting Duplicate Letters

Many candidates count:

b
a
l
o
n

and forget that:

l = 2
o = 2

are required.

Using Total Frequency Only

Having:

l = 1

does not allow even one balloon.

Simulating Unnecessarily

While simulation works, the minimum-frequency formula is cleaner and more efficient.

Key Takeaways

  1. This problem is based on frequency counting.
  2. Only five characters matter:
  3. b
  4. a
  5. l
  6. o
  7. n
  8. Characters l and o require special handling because they appear twice.
  9. The optimal solution uses a frequency array and a minimum calculation.
  10. Understanding bottleneck resources is a common interview pattern.

Conclusion

LeetCode 1189: Maximum Number of Balloons is a simple but powerful frequency-counting problem. While a simulation-based approach works correctly, the most elegant solution comes from recognizing that the answer is determined by the limiting character count.

Mastering this pattern will help you solve many string, HashMap, and counting-based interview questions efficiently.

Related Articles

Check if All Characters Have Equal Number of Occurrences – Frequency Map Approach (LeetCode 1941)

Check if All Characters Have Equal Number of Occurrences – Frequency Map Approach (LeetCode 1941)

Simple HashMap Technique to Validate Equal Character Frequencies

Read Article
LeetCode 387: First Unique Character in a String – Java HashMap Solution Explained

LeetCode 387: First Unique Character in a String – Java HashMap Solution Explained

Learn how to solve LeetCode 387 First Unique Character in a String using HashMap in Java. Includes brute force approach, optimized solution, intuition, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
LeetCode 2784: Check if Array is Good – Java HashMap Solution Explained

LeetCode 2784: Check if Array is Good – Java HashMap Solution Explained

Learn how to solve LeetCode 2784 Check if Array is Good using HashMap and counting techniques in Java. Includes brute force intuition, optimized approach, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
Ransom Note – Frequency Counting Made Simple (LeetCode 383)

Ransom Note – Frequency Counting Made Simple (LeetCode 383)

Using HashMap to Validate Character Availability Efficiently

Read Article
Ai Assistant Kas