What is the time complexity of Hash Map Counting approach?

O(n) where n is the length of text, as we iterate through the string once and perform O(1) hash map operations.

What is the space complexity of Array-based Counting approach?

O(1) since we use a fixed-size array of 26 elements regardless of input size.

Why do we divide 'l' and 'o' counts by 2?

The word 'balloon' contains two 'l' characters and two 'o' characters, so we need half as many of these letters compared to 'b', 'a', and 'n'.

Which approach is more efficient for this problem?

Array-based counting is slightly more efficient due to better cache locality and no hash computation overhead, though both are O(n) time.

Maximum Number of Balloons

Difficulty: Easy | Acceptance: 60.20% | Paid: No Topics: Hash Table, String, Counting

Given a string text, you want to use the characters of text to form as many instances of the word “balloon” as possible.

Each character can be used at most once. Return the maximum number of instances that can be formed.

Examples
Constraints
Hash Map Counting
Array-based Counting

Examples

Input: text = "nlaebolko"
Output: 1
Explanation: One 'balloon' can be formed using one 'b', one 'a', one 'l', one 'o', and one 'n'.

Input: text = "loonbalxballpoon"
Output: 2
Explanation: Two 'balloon' instances can be formed using the characters in the string.

Input: text = "leetcode"
Output: 0
Explanation: None of the characters required for 'balloon' are present in sufficient quantity.

Constraints

1 <= text.length <= 10⁴
text consists of lower case English letters only.

Hash Map Counting

Intuition Count the frequency of each character in the text using a hash map, then determine how many complete “balloon” words can be formed by finding the limiting character.

Steps

Create a hash map to count occurrences of each character in text.
The word “balloon” requires: b:1, a:1, l:2, o:2, n:1
Return the minimum of (count[‘b’], count[‘a’], count[‘l’]/2, count[‘o’]/2, count[‘n’])

python

from collections import Counter

class Solution:
    def maxNumberOfBalloons(self, text: str) -&gt; int:
        count = Counter(text)
        return min(count.get('b', 0), count.get('a', 0), count.get('l', 0) // 2, count.get('o', 0) // 2, count.get('n', 0))

Complexity

Time: O(n) where n is the length of text
Space: O(1) since we only store at most 26 characters
Notes: Hash map provides O(1) average lookup time

Array-based Counting

Intuition Use a fixed-size array of 26 elements to count character frequencies, which is more memory-efficient than a hash map for this specific problem.

Steps

Initialize an array of size 26 with zeros (one for each lowercase letter).
For each character in text, increment the corresponding index using character offset.
Calculate the result based on the counts of ‘b’, ‘a’, ‘l’, ‘o’, ‘n’.

python

class Solution:
    def maxNumberOfBalloons(self, text: str) -&gt; int:
        count = [0] * 26
        for c in text:
            count[ord(c) - ord('a')] += 1
        return min(count[ord('b') - ord('a')], count[ord('a') - ord('a')], count[ord('l') - ord('a')] // 2, count[ord('o') - ord('a')] // 2, count[ord('n') - ord('a')])

Complexity

Time: O(n) where n is the length of text
Space: O(1) fixed array of 26 integers
Notes: More cache-friendly than hash map approach