Maximum Number of Balloons — LeetCode 1189 Python Solution

The problem

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.

Example

Input

text = "nlaebolko"

Output

1

Python solution

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        cnt = Counter(text)
        cnt['o'] >>= 1
        cnt['l'] >>= 1
        return min(cnt[c] for c in 'balon')

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1189. Maximum Number of Balloons is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table and Counting.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems