Jobs

Interviews

Discussions

Maximum Number of Balloons

Easy

Wayfair

3 views

Topics:

StringsGreedy Algorithms

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 <= 10⁴
text consists of lower case English letters only.

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

Try coding it in LeetCode

Maximum Number of Balloons

Easy

Wayfair

3 views

Topics:

StringsGreedy Algorithms

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 <= 10⁴
text consists of lower case English letters only.

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the input string case-sensitive?
Can the input text string be empty or null?
If the input string cannot form the word 'balloon' even once, what value should I return?
Are there any constraints on the length of the input text string?
Besides lowercase English letters, can the input text string contain any other characters (e.g., spaces, numbers, symbols)?

Brute Force Solution

Approach

The brute force method for this problem means trying out all possible combinations of forming the word 'balloon' from the given text. We essentially check every possible arrangement of letters to see how many complete 'balloon' words we can make. This is done by manually trying out every possible mapping between the letters in the text and the letters in 'balloon'.

Here's how the algorithm would work step-by-step:

First, consider the first 'b' in the word 'balloon'. Search for every 'b' in the given text and mark each one as a potential starting point.
For each potential 'b', find every 'a' in the remaining text. Each of these 'a's could be the second letter in a potential 'balloon' word.
For each 'b' and 'a' pair, search for every 'l' in the remaining text. Since 'balloon' has two 'l's, we need to find pairs of 'l's.
For each 'b', 'a', and 'l' pair, search for every 'o' in the remaining text. Since 'balloon' has two 'o's, we need to find pairs of 'o's.
Finally, for each 'b', 'a', 'l', and 'o' selection, look for a 'n' in the remaining text.
If we find a combination of 'b', 'a', two 'l's, two 'o's, and an 'n', we've found one 'balloon' word. Mark these letters as used.
Repeat the entire process from the beginning, searching for another 'balloon' word using the letters that haven't been marked as used.
Keep track of how many complete 'balloon' words you find by trying out all these letter combinations.
The maximum number of complete 'balloon' words you find across all the attempts is the answer.

Code Implementation

def max_number_of_balloons_brute_force(text):
    maximum_balloons = 0

    def find_balloons(remaining_text, used_indices):
        nonlocal maximum_balloons
        found_balloon = False

        for b_index in range(len(remaining_text)):
            if remaining_text[b_index] == 'b' and b_index not in used_indices:
                for a_index in range(len(remaining_text)):
                    if remaining_text[a_index] == 'a' and a_index not in used_indices:

                        # Need two 'l's
                        l_indices = [index for index in range(len(remaining_text)) if remaining_text[index] == 'l' and index not in used_indices]
                        if len(l_indices) < 2:
                            continue

                        for l1_index in range(len(l_indices)):
                            for l2_index in range(l1_index + 1, len(l_indices)):
                                first_l_index = l_indices[l1_index]
                                second_l_index = l_indices[l2_index]
                                # Need two 'o's
                                o_indices = [index for index in range(len(remaining_text)) if remaining_text[index] == 'o' and index not in used_indices]

                                if len(o_indices) < 2:
                                    continue

                                for o1_index in range(len(o_indices)):
                                    for o2_index in range(o1_index + 1, len(o_indices)):
                                        first_o_index = o_indices[o1_index]
                                        second_o_index = o_indices[o2_index]

                                        for n_index in range(len(remaining_text)):
                                            if remaining_text[n_index] == 'n' and n_index not in used_indices:
                                                found_balloon = True

                                                # Mark indices as used
                                                new_used_indices = used_indices.copy()
                                                new_used_indices.add(b_index)
                                                new_used_indices.add(a_index)
                                                new_used_indices.add(first_l_index)
                                                new_used_indices.add(second_l_index)
                                                new_used_indices.add(first_o_index)
                                                new_used_indices.add(second_o_index)
                                                new_used_indices.add(n_index)

                                                find_balloons(remaining_text, new_used_indices)
                                                break
                                        if found_balloon:
                                            break
                                if found_balloon:
                                    break
                        if found_balloon:
                            break
                if found_balloon:
                    break
        if not found_balloon:
            # Base case: no more balloons can be formed
            balloons_formed = 0
            all_indices = set(range(len(text)))
            unused_indices = all_indices
            maximum_balloons = max(maximum_balloons, count_balloons(text))

    def count_balloons(text):
        letter_counts = {}
        for char in text:
            letter_counts[char] = letter_counts.get(char, 0) + 1

        # Integer division to determine the maximum number of balloons
        num_balloons = min(
            letter_counts.get('b', 0),
            letter_counts.get('a', 0),
            letter_counts.get('l', 0) // 2,
            letter_counts.get('o', 0) // 2,
            letter_counts.get('n', 0)
        )
        return num_balloons

    # Start the recursive search with an empty set of used indices
    find_balloons(text, set())

    return count_balloons(text)

# Counting method to get the balloon count for a candidate set of letters.
# This is called to find the number of balloons after recursion is stopped.

Big(O) Analysis

Time Complexity

O(n^7) – The provided brute force solution searches for each letter of 'balloon' sequentially within the input string of length n. Finding each 'b' requires iterating through the entire string (n). For each 'b', finding an 'a' also requires iterating (n). Then finding two 'l's requires nested loops (n^2). Similarly, finding two 'o's after that takes another nested loop (n^2). Finally, finding an 'n' takes another iteration (n). Therefore, the total complexity becomes O(n * n * n^2 * n^2 * n), which simplifies to O(n^7).

Space Complexity

O(N) – The brute force approach described in the plain English explanation involves marking letters as used. This would likely require an auxiliary data structure, such as a boolean array or a set, to keep track of which letters in the input string have been used to form 'balloon' words. The size of this data structure would be proportional to the length of the input text, which we denote as N. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The key is to realize we only need to count the occurrences of certain letters and then see how many times we can form the word 'balloon' given those counts. We focus on finding the limiting factor – the letter that appears the fewest times relative to how many times it's needed in 'balloon'.

Here's how the algorithm would work step-by-step:

First, count how many times each letter appears in the given text.
Next, identify the letters needed to spell 'balloon': 'b', 'a', 'l', 'o', and 'n'.
Now, determine how many times you can make the word 'balloon' based on the letter 'b'. For example, if 'b' appears 3 times, you can make 'balloon' at most 3 times.
Repeat the same process for the letters 'a' and 'n'.
Since 'l' and 'o' appear twice in 'balloon', divide their counts by 2 (ignoring any remainder). For example, if 'l' appears 7 times, consider it as 3 whole times. This is because you need two 'l's for each balloon.
Find the smallest of all those counts (the counts for 'b', 'a', 'l', 'o', and 'n'). This smallest count is the maximum number of times you can spell 'balloon' using the letters in the text.

Code Implementation

def max_number_of_balloons(text):
    letter_counts = {}
    for letter in text:
        letter_counts[letter] = letter_counts.get(letter, 0) + 1

    # We only care about these letters.
    balloon_letters = ['b', 'a', 'l', 'o', 'n']
    required_counts = {}

    for letter in balloon_letters:
        if letter not in letter_counts:
            return 0

    # Determine how many 'balloon' words can be formed.
    required_counts['b'] = letter_counts.get('b', 0)
    required_counts['a'] = letter_counts.get('a', 0)
    required_counts['n'] = letter_counts.get('n', 0)

    # Integer division because we need a whole number of balloons.
    required_counts['l'] = letter_counts.get('l', 0) // 2

    # Integer division because we need a whole number of balloons.
    required_counts['o'] = letter_counts.get('o', 0) // 2

    # The minimum is the limiting factor.
    return min(required_counts.values())

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input text of size n once to count the occurrences of each character. After counting, only a constant number of operations are performed to find the minimum count of the necessary characters ('b', 'a', 'l', 'o', 'n') required to form the word 'balloon'. Since the counting phase dominates the cost and involves iterating through the input text once, the time complexity is directly proportional to the input size n, making it O(n).

Space Complexity

O(1) – The algorithm uses a fixed-size hash map (or array) to store the counts of characters 'b', 'a', 'l', 'o', and 'n'. The size of this map is independent of the input string's length, N. Therefore, the auxiliary space used is constant. No other significant data structures are allocated, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Null or empty text input	Return 0, as no balloons can be formed without any characters.
Input text shorter than the word 'balloon'	Return 0 because it's impossible to form even a single 'balloon'.
Input text containing none of the required characters (b, a, l, o, n)	Return 0, as 'balloon' cannot be constructed.
Input text with only one instance of 'l' or 'o'	Return 0, since 'balloon' requires two of each of these characters.
Extremely long input string	Ensure counting operations using character frequency do not cause memory issues.
Input text with an extremely high frequency of one particular character like 'b'	The character counts will likely limit the number of 'balloon' words formed.
Integer overflow when counting characters	Use a data type large enough to store the counts or use modulo arithmetic.
Input contains unicode or extended ASCII characters outside a-z.	Only count the characters 'b', 'a', 'l', 'o', and 'n' and ignore all others

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the input string case-sensitive?
Can the input text string be empty or null?
If the input string cannot form the word 'balloon' even once, what value should I return?
Are there any constraints on the length of the input text string?
Besides lowercase English letters, can the input text string contain any other characters (e.g., spaces, numbers, symbols)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider the first 'b' in the word 'balloon'. Search for every 'b' in the given text and mark each one as a potential starting point.
For each potential 'b', find every 'a' in the remaining text. Each of these 'a's could be the second letter in a potential 'balloon' word.
For each 'b' and 'a' pair, search for every 'l' in the remaining text. Since 'balloon' has two 'l's, we need to find pairs of 'l's.
For each 'b', 'a', and 'l' pair, search for every 'o' in the remaining text. Since 'balloon' has two 'o's, we need to find pairs of 'o's.
Finally, for each 'b', 'a', 'l', and 'o' selection, look for a 'n' in the remaining text.
If we find a combination of 'b', 'a', two 'l's, two 'o's, and an 'n', we've found one 'balloon' word. Mark these letters as used.
Repeat the entire process from the beginning, searching for another 'balloon' word using the letters that haven't been marked as used.
Keep track of how many complete 'balloon' words you find by trying out all these letter combinations.
The maximum number of complete 'balloon' words you find across all the attempts is the answer.

Code Implementation

def max_number_of_balloons_brute_force(text):
    maximum_balloons = 0

    def find_balloons(remaining_text, used_indices):
        nonlocal maximum_balloons
        found_balloon = False

        for b_index in range(len(remaining_text)):
            if remaining_text[b_index] == 'b' and b_index not in used_indices:
                for a_index in range(len(remaining_text)):
                    if remaining_text[a_index] == 'a' and a_index not in used_indices:

                        # Need two 'l's
                        l_indices = [index for index in range(len(remaining_text)) if remaining_text[index] == 'l' and index not in used_indices]
                        if len(l_indices) < 2:
                            continue

                        for l1_index in range(len(l_indices)):
                            for l2_index in range(l1_index + 1, len(l_indices)):
                                first_l_index = l_indices[l1_index]
                                second_l_index = l_indices[l2_index]
                                # Need two 'o's
                                o_indices = [index for index in range(len(remaining_text)) if remaining_text[index] == 'o' and index not in used_indices]

                                if len(o_indices) < 2:
                                    continue

                                for o1_index in range(len(o_indices)):
                                    for o2_index in range(o1_index + 1, len(o_indices)):
                                        first_o_index = o_indices[o1_index]
                                        second_o_index = o_indices[o2_index]

                                        for n_index in range(len(remaining_text)):
                                            if remaining_text[n_index] == 'n' and n_index not in used_indices:
                                                found_balloon = True

                                                # Mark indices as used
                                                new_used_indices = used_indices.copy()
                                                new_used_indices.add(b_index)
                                                new_used_indices.add(a_index)
                                                new_used_indices.add(first_l_index)
                                                new_used_indices.add(second_l_index)
                                                new_used_indices.add(first_o_index)
                                                new_used_indices.add(second_o_index)
                                                new_used_indices.add(n_index)

                                                find_balloons(remaining_text, new_used_indices)
                                                break
                                        if found_balloon:
                                            break
                                if found_balloon:
                                    break
                        if found_balloon:
                            break
                if found_balloon:
                    break
        if not found_balloon:
            # Base case: no more balloons can be formed
            balloons_formed = 0
            all_indices = set(range(len(text)))
            unused_indices = all_indices
            maximum_balloons = max(maximum_balloons, count_balloons(text))

    def count_balloons(text):
        letter_counts = {}
        for char in text:
            letter_counts[char] = letter_counts.get(char, 0) + 1

        # Integer division to determine the maximum number of balloons
        num_balloons = min(
            letter_counts.get('b', 0),
            letter_counts.get('a', 0),
            letter_counts.get('l', 0) // 2,
            letter_counts.get('o', 0) // 2,
            letter_counts.get('n', 0)
        )
        return num_balloons

    # Start the recursive search with an empty set of used indices
    find_balloons(text, set())

    return count_balloons(text)

# Counting method to get the balloon count for a candidate set of letters.
# This is called to find the number of balloons after recursion is stopped.

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, count how many times each letter appears in the given text.
Next, identify the letters needed to spell 'balloon': 'b', 'a', 'l', 'o', and 'n'.
Now, determine how many times you can make the word 'balloon' based on the letter 'b'. For example, if 'b' appears 3 times, you can make 'balloon' at most 3 times.
Repeat the same process for the letters 'a' and 'n'.
Since 'l' and 'o' appear twice in 'balloon', divide their counts by 2 (ignoring any remainder). For example, if 'l' appears 7 times, consider it as 3 whole times. This is because you need two 'l's for each balloon.
Find the smallest of all those counts (the counts for 'b', 'a', 'l', 'o', and 'n'). This smallest count is the maximum number of times you can spell 'balloon' using the letters in the text.

Code Implementation

def max_number_of_balloons(text):
    letter_counts = {}
    for letter in text:
        letter_counts[letter] = letter_counts.get(letter, 0) + 1

    # We only care about these letters.
    balloon_letters = ['b', 'a', 'l', 'o', 'n']
    required_counts = {}

    for letter in balloon_letters:
        if letter not in letter_counts:
            return 0

    # Determine how many 'balloon' words can be formed.
    required_counts['b'] = letter_counts.get('b', 0)
    required_counts['a'] = letter_counts.get('a', 0)
    required_counts['n'] = letter_counts.get('n', 0)

    # Integer division because we need a whole number of balloons.
    required_counts['l'] = letter_counts.get('l', 0) // 2

    # Integer division because we need a whole number of balloons.
    required_counts['o'] = letter_counts.get('o', 0) // 2

    # The minimum is the limiting factor.
    return min(required_counts.values())

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty text input	Return 0, as no balloons can be formed without any characters.
Input text shorter than the word 'balloon'	Return 0 because it's impossible to form even a single 'balloon'.
Input text containing none of the required characters (b, a, l, o, n)	Return 0, as 'balloon' cannot be constructed.
Input text with only one instance of 'l' or 'o'	Return 0, since 'balloon' requires two of each of these characters.
Extremely long input string	Ensure counting operations using character frequency do not cause memory issues.
Input text with an extremely high frequency of one particular character like 'b'	The character counts will likely limit the number of 'balloon' words formed.
Integer overflow when counting characters	Use a data type large enough to store the counts or use modulo arithmetic.
Input contains unicode or extended ASCII characters outside a-z.	Only count the characters 'b', 'a', 'l', 'o', and 'n' and ignore all others