Maximum Number of Balloons

Good use-case for a counting array, seeing as we have a known range of letters. Think about how you can iterate over the letters we need, and compare to the minimum number of letters. The catch will be how you handle ’l’ and ‘o’, as you need two for one ‘balloon’.

Absolutely, you’ve got the intuition correct! We’ll count the frequencies of each character in the input string and then check how many times we can form the word “balloon” considering the frequency of each character in the word “balloon”.

  1. Identify and Initialize: Start by identifying the letters we need - ‘b’, ‘a’, ’l’, ‘o’, ’n’. Initialize a counter dictionary to keep track of the occurrences of these letters in the text.

  2. Counting: Iterate over the input string and for each character, if it is one of ‘b’, ‘a’, ’l’, ‘o’, ’n’, increment the respective counter.

  3. Calculating Instances: Now, we have the count of each character we need. To form the word “balloon”, we need 1 ‘b’, 1 ‘a’, 2 ’l’, 2 ‘o’, and 1 ’n’. So, we need to divide the count of ’l’ and ‘o’ by 2. The minimum count among these five letters will give us the maximum number of instances of “balloon” we can form.

  4. Returning Result: Return the minimum count.

Let’s keep in mind that this process works because the characters ’l’ and ‘o’ occur twice in the word “balloon”. Hence, we divide their counts by 2 before comparing. The process is a form of a counting sort, and the extra step is due to the double occurrence of certain characters. It’s a straightforward and elegant approach to solve this problem.

Let’s implement this approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        # Step 1: Identify and Initialize
        counter = {'b': 0, 'a': 0, 'l': 0, 'o': 0, 'n': 0}

        # Step 2: Counting
        for char in text:
            if char in counter:
                counter[char] += 1

        # Step 3: Calculating Instances
        counter['l'] //= 2
        counter['o'] //= 2

        # Step 4: Returning Result
        return min(counter.values())

This code first creates a dictionary to count the occurrence of each character in “balloon”. It then iterates through the input string, incrementing the count for each character. After that, it adjusts the counts for ’l’ and ‘o’ since each of them occurs twice in “balloon”. Finally, it returns the minimum count among the five characters, which represents the maximum number of instances of “balloon” that can be formed.

Q&A