Problem Statement in English

You’re 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.

Approach

To solve this problem, we can use a frequency counter to count the occurrences of each character in the input string text.

Then, we can determine how many times we can form the word “balloon” based on the frequency of its characters.

For each character in the word “balloon”, we will check how many times it appears in text and divide that by the number of times it appears in “balloon”. The minimum of these values will give us the maximum number of instances of “balloon” that can be formed.

And we’re done!

Solution in Python


class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        c = Counter(text)

        target = Counter("balloon")

        res = len(text)

        for k in target:
            res = min(res, c[k] // target[k])

        return res

Complexity

  • Time: $O(n)$
    Since we need to count the frequency of each character in the input string, the time complexity is linear with respect to the length of the string.

  • Space: $O(1)$
    Since the target string is fixed, the space used by the counter is constant.

And we are done.