Maximum Number Of Balloons - Leetcode Solution

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

Solution:

The problem statement asks us to form the word "balloon" from given text and return the maximum number of instances that can be formed. Here are the steps that can be followed to solve the problem:

1. Initialize a dictionary, say letter_counts, to keep track of the frequency of each character in text.

2. Initialize a variable, say count, to keep track of the minimum frequency of each character required to form "balloon". We can set count of 'b', 'a', 'n' to 1 and count of 'l', 'o' to 2.

3. Traverse the characters in the word "balloon" and update the count variable based on the frequency of each character in text.

4. Return the minimum of the count of each character obtained in step 3 as the maximum number of instances of "balloon" that can be formed.

Let's see the Python implementation:

def maxNumberOfBalloons(text: str) -> int:
    letter_counts = {}
    for letter in text:
        letter_counts[letter] = letter_counts.get(letter, 0) + 1
        
    b_count = letter_counts.get('b', 0)
    a_count = letter_counts.get('a', 0)
    n_count = letter_counts.get('n', 0)
    l_count = letter_counts.get('l', 0) // 2
    o_count = letter_counts.get('o', 0) // 2
    
    count = min(b_count, a_count, n_count, l_count, o_count)
    
    return count

In the above code, we first initialize a dictionary, letter_counts to keep track of frequency of each letter in text. Then, we obtain the frequency of each character in text and set count variable to the minimum frequency of each character required to form "balloon". Finally, we return the count variable as the maximum number of instances of "balloon" that can be formed.

Time Complexity: O(n) where n is the length of the given text.

Space Complexity: O(1) as the size of the dictionary used is constant.

1