Skip to main content
Talentd

Maximum Number of Balloons - Solution & Explanation

EasyHash TableStringCounting20 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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.

 

Example 1:

Input: text = "nlaebolko"
Output: 1

Example 2:

Input: text = "loonbalxballpoon"
Output: 2

Example 3:

Input: text = "leetcode"
Output: 0

 

Constraints:

  • 1 <= text.length <= 104
  • text consists of lower case English letters only.

 

Note: This question is the same as 2287: Rearrange Characters to Make Target String.

Approach Overview

Problem Overview: Given a string text, determine how many times you can form the word "balloon" using the characters in the string. Each character in text can be used only once per instance of the word.

Approach 1: Frequency Count Method (O(n) time, O(1) space)

Count how many times each character appears in the input string. A simple array of size 26 or a hash map works well for this hash table counting pattern. After building the frequency map, check how many complete "balloon" words can be formed. The word requires b=1, a=1, l=2, o=2, and n=1. Divide the counts of l and o by 2 since they appear twice in the target word. The smallest resulting value across these characters determines the maximum number of balloons you can build.

This approach scans the string once, performs constant-time updates, and then checks a fixed set of characters. Time complexity is O(n), and space complexity is O(1) because the alphabet size is constant. This pattern appears frequently in string counting problems.

Approach 2: Character Frequency Ratio Method (O(n) time, O(1) space)

This method treats the problem as a ratio comparison between the characters in text and the required characters of the word "balloon". First compute the frequency of characters in the input string using a counting array. Then compute the ratio count[c] / required[c] for each character needed in the target word. For example, if text contains 6 l characters and the word requires 2, that contributes 6 / 2 = 3 possible uses.

The answer is the minimum ratio among all required characters. This guarantees that every instance of "balloon" has enough letters available. Like the previous method, the algorithm processes the string once and performs constant work afterward. Time complexity remains O(n), and space complexity stays O(1). Conceptually this frames the problem as a constrained resource allocation problem based on counting.

Recommended for interviews: The frequency count approach is what most interviewers expect. It demonstrates that you recognize a character counting pattern and can translate the requirements of the target word into frequency constraints. The ratio interpretation is equally efficient but mainly reframes the same idea mathematically. Showing the counting solution first proves you understand the core pattern used in many string and hash table interview problems.

Approach 1: Frequency Count Method

This approach involves counting the frequency of each character in the string 'text' and then determining how many full instances of the word 'balloon' can be formed based on these frequencies. We will count the occurrences of the characters 'b', 'a', 'l', 'o', and 'n'. Since 'l' and 'o' appear twice in the word 'balloon', their counts should be halved. Finally, we find the minimum number of complete 'balloon' words that can be formed using these character counts.

The C solution uses an array of size 26 to store the frequency of each letter in the input string 'text'. The count for 'l' and 'o' is divided by two because they appear twice in 'balloon'. Finally, it calculates the minimum count required among 'b', 'a', 'l', 'o', and 'n' to determine how many instances of 'balloon' can be formed.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), since we are using a constant amount of extra space.

Try this approach in the editor →

Approach 2: Character Frequency Ratio Method

Instead of counting characters explicitly, this approach calculates the maximum number of 'balloon' instances by directly comparing the ratios of character counts required. Specifically, for 'b', 'a', and 'n', the ratio is 1:1, but for 'l' and 'o', the ratio is 1:2 in 'balloon'. This approach simplifies checking character sufficiency by calculating the feasible number of 'balloon' words based on the complete sets of these character combinations.

This C solution defines separate counts for each character directly required to form 'balloon'. It then computes how many full 'balloon' sets can be constructed based on these adjusted character counts, particularly halving the 'l' and 'o' counts.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), as it uses a fixed number of variables for counting.

Try this approach in the editor →

Approach 3: Counting

We count the frequency of each letter in the string text, and then divide the frequency of the letters 'o' and 'l' by 2, because the word balloon contains the letters 'o' and 'l' twice.

Next, we traverse each letter in the word balon, and find the minimum frequency of each letter in the string text. This minimum frequency is the maximum number of times the word balloon can appear in the string text.

The time complexity is O(n), and the space complexity is O(C). Here, n is the length of the string text, and C is the size of the character set. In this problem, C = 26.

Code

PythonJavaC++GoTypeScriptRustPHP

Python

Java

C++

Go

TypeScript

Rust

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Frequency Count Method

Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), since we are using a constant amount of extra space.

Character Frequency Ratio Method

Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), as it uses a fixed number of variables for counting.

Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Frequency Count MethodO(n)O(1)General solution for string character counting problems
Character Frequency Ratio MethodO(n)O(1)When modeling the problem as resource ratios between available and required characters

Video Solution

Maximum Number of Balloons - Leetcode 1189 - Python • NeetCode • 28,854 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Number of Balloons easy or hard?
Maximum Number of Balloons is classified as an Easy problem on LeetCode with a moderate acceptance rate around 60%. The difficulty comes from recognizing that some characters in "balloon" appear twice, which requires dividing their counts when calculating the final answer.
How to solve Maximum Number of Balloons in O(n)?
Iterate through the string and count the frequency of each character using an array or hash map. After counting, compute the number of possible "balloon" words by evaluating b, a, l/2, o/2, and n. The smallest of these values is the result. This requires one pass through the string and constant extra memory.
What is the best approach for Maximum Number of Balloons?
The best approach uses character frequency counting. Count how many times each letter appears in the string, then determine how many "balloon" words can be formed by checking the required counts of b, a, l, o, and n. Since l and o appear twice, divide their counts by two. The minimum value among these determines the answer in O(n) time and O(1) space.
Is Maximum Number of Balloons asked at Google/Amazon/Meta?
This problem represents a common string frequency counting pattern frequently used in technical interviews at large tech companies. Variations of character counting and resource allocation problems appear in interviews at companies like Amazon, Google, and Meta when evaluating hash table and string manipulation skills.
What data structure is used in Maximum Number of Balloons?
The primary data structure is a hash table or a fixed-size frequency array. It stores how many times each character appears in the string. Because the input consists of lowercase English letters, many solutions use an integer array of size 26 for constant-time updates and lookups.
What is the time complexity of Maximum Number of Balloons?
The optimal solution runs in O(n) time where n is the length of the input string. The algorithm scans the string once to build character frequencies and then performs a constant number of checks for the letters in "balloon". Space complexity is O(1) because the frequency array size is fixed at 26 letters.
Maximum Number of Balloons Python or Java solution approach?
Both Python and Java implementations follow the same idea: count character frequencies and compute the limiting character among b, a, l/2, o/2, and n. Python often uses collections.Counter, while Java typically uses an int[26] array. Both implementations achieve O(n) time and O(1) space complexity.

Ready to solve this problem?

Practice Maximum Number of Balloons with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters