# Maximum Number of Balloons
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-number-of-balloons)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-balloons
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [Tesla](https://scaleengineer.com/companies/tesla), [Wayfair](https://scaleengineer.com/companies/wayfair)
---
## 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.

**Example 1:**

**![](https://assets.glich.co/dsa/maximum-number-of-balloons/image0.JPG)**

**Input:** text = "nlaebolko"
**Output:** 1

**Example 2:**

**![](https://assets.glich.co/dsa/maximum-number-of-balloons/image1.JPG)**

**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.](https://leetcode.com/problems/rearrange-characters-to-make-target-string/description/)

# Approaches
## Brute Force Simulation
This approach simulates the process of forming the word 'balloon' one by one. It repeatedly scans the input string to find and 'use up' the necessary characters ('b', 'a', 'l', 'l', 'o', 'o', 'n') for one instance of 'balloon'. The process continues until the required characters for a new 'balloon' cannot be found.
**Time:** O(N^2), where N is the length of the input string `text`. In the worst case, we can form `k = N/7` balloons. For each balloon, we iterate through the `balloon` string (7 characters) and for each character, we search and remove from a list of size up to N. Searching (`contains`) and removing (`remove(Object)`) from an `ArrayList` both take O(N) time. Thus, the complexity is roughly `k * 7 * N`, which simplifies to O(N^2). · **Space:** O(N), where N is the length of `text`. We need to store a copy of the input string in a mutable data structure like an `ArrayList`.
**Pros:** Simple to understand and conceptualize.; Directly follows the logic described in the problem statement.
**Cons:** Extremely inefficient with a time complexity of O(N^2).; Becomes very slow for large input strings, likely leading to a 'Time Limit Exceeded' error on coding platforms.; Uses O(N) extra space to store a mutable copy of the string.
### Explanation
We can model this by converting the input string into a more mutable data structure, like a list of characters. We then enter a loop. In each iteration, we attempt to find and remove one 'b', one 'a', two 'l's, two 'o's, and one 'n'. If we successfully remove all seven characters, we increment our count of formed 'balloons' and continue to the next iteration. If at any point we fail to find a required character, it means we cannot form another 'balloon', so we break the loop and return the current count. This method is intuitive but inefficient because it involves multiple passes over a shrinking data structure.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int maxNumberOfBalloons(String text) {
        List<Character> charList = new ArrayList<>();
        for (char c : text.toCharArray()) {
            charList.add(c);
        }

        int balloonsCount = 0;
        String balloon = "balloon";

        while (true) {
            boolean canForm = true;
            for (char ch : balloon.toCharArray()) {
                if (charList.contains(ch)) {
                    // remove(Object) is important here to remove the character, not by index
                    charList.remove(Character.valueOf(ch));
                } else {
                    canForm = false;
                    break;
                }
            }

            if (canForm) {
                balloonsCount++;
            } else {
                break;
            }
        }
        return balloonsCount;
    }
}
```
### Algorithm
- Initialize `balloonsCount` to 0.
- Convert the input `text` string to a mutable list of characters, for example, an `ArrayList`.
- Start a loop that continues indefinitely (`while(true)`).
- Inside the loop, attempt to find and remove the characters required for one "balloon": 'b', 'a', 'l', 'l', 'o', 'o', 'n'.
- Use a boolean flag, `canForm`, initialized to `true` at the start of each iteration.
- For each character in the word "balloon", check if it exists in the list. If it does, remove one occurrence. If it doesn't, set `canForm` to `false` and stop checking for the current iteration.
- After checking all characters for one "balloon", if `canForm` is still `true`, it means a balloon was successfully formed, so increment `balloonsCount`.
- If `canForm` is `false`, it means we couldn't find all the necessary characters, so we break out of the main loop.
- Finally, return `balloonsCount`.

## Frequency Counting with HashMap
A much more efficient approach is to count the frequency of each character in the input string `text` first. After counting, we can directly calculate how many 'balloons' can be formed. The number of 'balloons' is limited by the character that is least available, considering that 'l' and 'o' are needed twice.
**Time:** O(N), where N is the length of `text`. We iterate through the string once to build the frequency map. The subsequent operations (map lookups and finding the minimum) take constant time. · **Space:** O(k), where k is the number of unique characters in `text`. Since the input is restricted to lowercase English letters, k is at most 26. Therefore, the space complexity is considered constant, O(1).
**Pros:** Highly efficient with a linear time complexity.; Optimal time complexity as we must inspect every character at least once.; Uses constant extra space, as the number of unique characters is fixed (at most 26).; More general than the array approach; it would work for any character set (e.g., Unicode) without modification.
**Cons:** Uses a HashMap, which has some constant factor overhead due to hashing and potential collisions compared to a simple array.; Slightly more complex to write than the array-based approach for this specific problem.
### Explanation
This method involves a single pass through the input string to build a frequency map (a `HashMap`) of all its characters. Once we have the counts of every character, we can determine the maximum number of 'balloons'. We need one 'b', one 'a', and one 'n', but two 'l's and two 'o's for each 'balloon'. Therefore, the number of 'balloons' is limited by `count('b')`, `count('a')`, `count('n')`, `count('l') / 2`, and `count('o') / 2`. The final answer is the minimum of these five values.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxNumberOfBalloons(String text) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : text.toCharArray()) {
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }

        int countB = counts.getOrDefault('b', 0);
        int countA = counts.getOrDefault('a', 0);
        int countL = counts.getOrDefault('l', 0);
        int countO = counts.getOrDefault('o', 0);
        int countN = counts.getOrDefault('n', 0);

        // For 'l' and 'o', we need two for each balloon.
        int result = Math.min(countB, countA);
        result = Math.min(result, countL / 2);
        result = Math.min(result, countO / 2);
        result = Math.min(result, countN);

        return result;
    }
}
```
### Algorithm
- Create a `HashMap<Character, Integer>` to store the frequency of each character.
- Iterate through each character `c` of the input string `text`.
- For each character, update its count in the HashMap. If the character is already a key, increment its value; otherwise, add it with a value of 1. This can be done efficiently using `map.put(c, map.getOrDefault(c, 0) + 1)`.
- After populating the map, retrieve the counts for the characters required for "balloon": 'b', 'a', 'l', 'o', 'n'. Use `map.getOrDefault(char, 0)` to safely get counts, which will be 0 if the character is not present in `text`.
- Calculate the number of "balloons" that can be formed from 'l's and 'o's by dividing their counts by 2 (using integer division).
- The maximum number of "balloons" is limited by the least available character. Find the minimum of the following five values: `count('b')`, `count('a')`, `count('l')/2`, `count('o')/2`, and `count('n')`.
- Return this minimum value.

## Frequency Counting with an Array
This approach is an optimization of the frequency counting method. Since the input string consists only of lowercase English letters, we can use a fixed-size array of 26 integers instead of a HashMap to store character frequencies. This is generally faster in practice due to direct memory access and better cache locality.
**Time:** O(N), where N is the length of `text`. We perform a single pass over the string to count frequencies. All other operations are constant time. · **Space:** O(1). We use an integer array of fixed size 26, which does not depend on the input size.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Extremely fast in practice due to the use of an array, which avoids hashing overhead and benefits from cache-friendly contiguous memory access.
**Cons:** This specific optimization is only applicable because the character set is known and small (e.g., lowercase English letters). It is less flexible than a HashMap if the character set were larger or unknown.
### Explanation
We initialize an integer array of size 26 to all zeros. Each index in the array corresponds to a letter of the alphabet (e.g., index 0 for 'a', index 1 for 'b', etc.). We make a single pass through the input string `text`. For each character, we increment the count at the corresponding index in our frequency array. After populating the array, we retrieve the counts for 'b', 'a', 'l', 'o', 'n' by accessing the appropriate indices. The logic to calculate the maximum number of 'balloons' remains the same: find the minimum of `count('b')`, `count('a')`, `count('l') / 2`, `count('o') / 2`, and `count('n')`.

```java
class Solution {
    public int maxNumberOfBalloons(String text) {
        int[] charCounts = new int[26];
        for (char c : text.toCharArray()) {
            charCounts[c - 'a']++;
        }

        int countB = charCounts['b' - 'a'];
        int countA = charCounts['a' - 'a'];
        int countL = charCounts['l' - 'a'];
        int countO = charCounts['o' - 'a'];
        int countN = charCounts['n' - 'a'];

        // Find the minimum number of balloons we can form.
        // The number of 'l's and 'o's must be divided by 2.
        int min = countB;
        min = Math.min(min, countA);
        min = Math.min(min, countL / 2);
        min = Math.min(min, countO / 2);
        min = Math.min(min, countN);

        return min;
    }
}
```
### Algorithm
- Create an integer array, `charCounts`, of size 26, and initialize all its elements to 0. This array will store the frequency of each lowercase English letter.
- Iterate through each character `c` of the input string `text`.
- For each character, increment the count at the corresponding index in the array. The index can be calculated as `c - 'a'`. So, we perform `charCounts[c - 'a']++`.
- After the loop finishes, the `charCounts` array contains the frequency of every character in `text`.
- Retrieve the counts for the required characters by accessing the array at their respective indices: `countB = charCounts['b' - 'a']`, `countA = charCounts['a' - 'a']`, and so on.
- Calculate the number of "balloons" possible from 'l's and 'o's by dividing their counts by 2.
- The result is the minimum of the available counts: `min(countB, countA, countL/2, countO/2, countN)`.
- Return this final minimum value.

# Solutions
### Java

```java
class Solution {
public
  int maxNumberOfBalloons(String text) {
    int[] cnt = new int[26];
    for (int i = 0; i < text.length(); ++i) {
      ++cnt[text.charAt(i) - 'a'];
    }
    cnt['l' - 'a'] >>= 1;
    cnt['o' - 'a'] >>= 1;
    int ans = 1 << 30;
    for (char c : "balon".toCharArray()) {
      ans = Math.min(ans, cnt[c - 'a']);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxNumberOfBalloons(string text) {
    int cnt[26]{};
    for (char c : text) {
      ++cnt[c - 'a'];
    }
    cnt['o' - 'a'] >>= 1;
    cnt['l' - 'a'] >>= 1;
    int ans = 1 << 30;
    string t = "balon";
    for (char c : t) {
      ans = min(ans, cnt[c - 'a']);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxNumberOfBalloons(self, text: str) -> int: cnt = Counter(text) cnt['o'] >>= 1 cnt['l'] >>= 1 return min(cnt[c] for c in 'balon')

```