Code Logo

Maximum Number of Balloons

Published at24 Jul 2026
Created by
Easy 0 views
Like0

Given a string text, you want to use the characters of text to form as many instances of the word 'balloon' as possible. Each character can be used at most once. Return the maximum number of 'balloon' instances that can be formed.

This is a frequency counting DP problem. Count how many times each required letter appears in the text: b, a, l, o, n. Since 'l' and 'o' appear twice in 'balloon', divide their counts by 2. The answer is the minimum among all five counts.

The DP state is the frequency map of characters. After counting, compute the bottleneck character: the one with the smallest count (after adjusting for double letters) determines how many complete 'balloon' words can be formed.

Edge cases include text missing one or more required letters (return 0), text with only lowercase letters, and case sensitivity (text contains only lowercase as per problem specification).

The balloon counting problem is a basic frequency DP where we count occurrences and then apply a divisor to find the bottleneck character. The minimum function identifies the limiting resource, a common pattern in resource allocation DP problems.

The min function finds the bottleneck character that limits how many 'balloon' words can be formed. This pattern of counting resources and dividing by usage rate is fundamental to resource allocation DP problems.

Example Input & Output

Example 1
Input
"nlaebolko"
Output
1
Explanation

Can form 1 "balloon".

Example 2
Input
"leetcode"
Output
0
Explanation

Missing required letters.

Example 3
Input
"balloon"
Output
1
Explanation

Exactly one.

Example 4
Input
"balloonballoon"
Output
2
Explanation

Two complete sets.

Example 5
Input
"loonbalxballpoon"
Output
2
Explanation

Can form 2 "balloon".

Algorithm Flow

Recommendation Algorithm Flow for Maximum Number of Balloons
Recommendation Algorithm Flow for Maximum Number of Balloons

Solution Approach

Count frequencies of b,a,l,o,n. Divide l and o by 2. Return the minimum count.

function solution(text) {
  var freq = {};
  for (var i = 0; i < text.length; i++) freq[text[i]] = (freq[text[i]] || 0) + 1;
  freq['l'] = Math.floor((freq['l'] || 0) / 2);
  freq['o'] = Math.floor((freq['o'] || 0) / 2);
  return Math.min(freq['b']||0, freq['a']||0, freq['l']||0, freq['o']||0, freq['n']||0);
}

Time O(n), Space O(1).

Best Answers

java
import java.util.*;
class Solution {
    public int solution(String text) {
        Map<Character,Integer> f=new HashMap<>();
        for (char ch:text.toCharArray()) f.put(ch,f.getOrDefault(ch,0)+1);
        int b=f.getOrDefault('b',0);
        int a=f.getOrDefault('a',0);
        int l=f.getOrDefault('l',0)/2;
        int o=f.getOrDefault('o',0)/2;
        int n=f.getOrDefault('n',0);
        return Math.min(Math.min(Math.min(b,a),Math.min(l,o)),n);
    }
}