Maximum Number of Balloons - Practice Coding Problems

Maximum Number of Balloons - Problem

Given a string text, you want to use the characters of text to form as many instances of the word "balloon" as possible.

You can use each character in text at most once. Return the maximum number of instances that can be formed.

Input & Output

Example 1 — Basic Case

$ Input: text = "nlaebolko"

› Output: 1

💡 Note: We have: n=1, l=2, a=1, e=1, b=1, o=2, k=1. For 'balloon' we need: b=1, a=1, l=2, o=2, n=1. We can form exactly 1 balloon.

Example 2 — Multiple Balloons

$ Input: text = "loonbalxballpoon"

› Output: 2

💡 Note: We have: l=4, o=4, n=3, b=2, a=2, x=1, p=1. For 'balloon' we need 1b+1a+2l+2o+1n each. We can form 2 balloons: min(2,2,4/2,4/2,3) = 2.

Example 3 — Insufficient Characters

$ Input: text = "leetcode"

› Output: 0

💡 Note: We have: l=1, e=3, t=1, c=1, o=1, d=1. Missing 'b', 'a', 'n' and insufficient 'l', 'o'. Cannot form any balloon.

Constraints

1 ≤ text.length ≤ 10⁴
text consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Given string with various characters

Character Counting

Count required letters: b, a, l, o, n

Calculate Result

Find limiting factor for complete balloons

Key Takeaway

🎯 Key Insight: The answer is determined by the character that appears least frequently relative to how many times it's needed in 'balloon'

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to count the frequency of each character needed for 'balloon' (b, a, l, o, n) and find the limiting factor. Since 'balloon' requires 2 l's and 2 o's but only 1 each of b, a, n, we calculate min(b_count, a_count, l_count/2, o_count/2, n_count). Best approach is frequency counting with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Frequency Counting	O(n)	O(k)	Use hash map to count all characters, then calculate result
Brute Force Character Counting	O(n)	O(1)	Count each character individually and calculate maximum balloons

Hash Map Frequency Counting — Algorithm Steps

Create frequency map of all characters
Check counts for required letters: b, a, l, o, n
Calculate maximum balloons based on limiting character

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Map

Count all character frequencies

Extract Needed

Get counts for b, a, l, o, n

Calculate

Find limiting factor for balloon formation

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(char* text) {
    // Count frequency using array (assuming lowercase letters)
    int freq[26] = {0};
    
    for (int i = 0; text[i] != '\0'; i++) {
        if (text[i] >= 'a' && text[i] <= 'z') {
            freq[text[i] - 'a']++;
        }
    }
    
    // Get counts for required characters
    // 'balloon' needs: 1 b, 1 a, 2 l, 2 o, 1 n
    int bCount = freq['b' - 'a'];
    int aCount = freq['a' - 'a'];
    int lCount = freq['l' - 'a'];
    int oCount = freq['o' - 'a'];
    int nCount = freq['n' - 'a'];
    
    // Calculate maximum balloons
    int result = bCount;
    result = min(result, aCount);
    result = min(result, lCount / 2);
    result = min(result, oCount / 2);
    result = min(result, nCount);
    
    return result;
}

int main() {
    char text[10001];
    fgets(text, sizeof(text), stdin);
    text[strcspn(text, "\n")] = 0;
    
    int result = solution(text);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to build frequency map plus constant time to check 5 characters

✓ Linear Growth

Space Complexity

O(k)

Hash map stores at most k unique characters from input

✓ Linear Space

28.0K Views

Medium Frequency

~10 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Frequency Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler