Scale Engineer

Maximum Number of Balloons

Easy
#1114Time: 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`.2 companies
Patterns
Counting
Data structures
Hash TableString
Companies
TeslaWayfair

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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`.

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem