💬 Discord
Sign In
NeetCode #56LC-1189EasyArrays & Hashing
← Back to All Problems

#56 · #1189 · Maximum Number of Balloons("气球"的最大数量)

📌 Problem Statement & Constraints

Given a string text of lowercase letters, return the maximum number of instances of the word "balloon" that can be formed using the letters of text. Each letter may be used at most once. Constraints: 1 <= text.length <= 10^4.

💡 Core Algorithmic Approaches

  1. Count the letters of text. The word "balloon" needs one b, one a, two l, two o, and one n.
  2. The number of complete copies is limited by the scarcest requirement, so compute min(count[c] // need[c]) over the five distinct letters.
  3. The division by 2 for l and o is the only subtlety; treating all letters as needing one copy each would overcount.
  4. If any required letter is absent, the counter returns 0 for it and the minimum is 0.

💻 Benchmark Python3 Implementation

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        from collections import Counter
        cnt = Counter(text)
        need = {"b": 1, "a": 1, "l": 2, "o": 2, "n": 1}
        return min(cnt[ch] // need[ch] for ch in need)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + k): O(n) to count, then a constant-size scan over the five required letters.
💾 Space Complexity
O(k) for the counter, with k <= 26.

⚠️ Interview Pitfalls & Follow-ups

  • Treating l and o as needing only one copy each: they appear twice in "balloon", so their counts must be halved.
  • Using min(cnt[ch] for ch in need) without dividing: same error, expressed differently.
  • Forgetting that letters not in need are irrelevant: cnt may contain many other letters; only the five matter.
  • Using float division: cnt[ch] // need[ch] must be integer division.