Maximum Number of Balloons - Leetcode 1189 - Hashmaps & Sets (Python)

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@battadileep5167]

you are the legend no one will beat u

[@swiftlyr6258]

Hmm I tried it on my own and came up with this:
class Solution:
def maxNumberOfBalloons(self, text: str) -> int:

word = "balloon"
count= Counter(text)
total=0

while True:
for c in word:
count[c]-=1
if count[c] < 0:
return total
total+=1
return total

[@JoeTan-nq4fq]

Use Counter class for shortcut. Then find min of single letters ('b', 'a', 'n') and double letters ('l', 'o'). Return min of single, double //2 if single and double is not zero, else return zero.

[@Ondho_biraal]

I did this
class Solution:
def maxNumberOfBalloons(self, text: str) -> int:
word = "balloon"
hash = {}
for x in text:
if x not in hash:
hash[x] = 1
else:
hash[x] += 1

i=0
count = 0
while True:
checkLetter = word[i]
if checkLetter not in hash:
break
elif hash[checkLetter] == 1:
del hash[checkLetter]
else:
hash[checkLetter] -= 1
i+=1
if checkLetter=='n':
i=0
count+=1
return count

[@rakshpatel]

Good explanation. However you are ignoring string balloon saying it is very small but while calculating time and space complexity it should matter as in other case you may have different string. So instead of O(1) you should consider O(m) where m is length of string balloon. So when you do membership test it is O(m) and shouldn’t be constant

[@ayushman-tech]

[Solution]
Don't over engineer, keep it simple:
def maxNumberOfBalloons(self, text: str) -> int:
count_b = count_a = count_l = count_o = count_n = 0
for char in text:
if char == 'b':
count_b += 1
elif char == 'a':
count_a += 1
elif char == 'l':
count_l += 1
elif char == 'o':
count_o += 1
elif char == 'n':
count_n += 1
return min(count_b, count_a, count_l // 2, count_o // 2, count_n)

[@mxcoyl]

Using a dictionary makes solution easier to explain, but if you map letters to array indices (with if-else in code) that should save some time on hash calculations and accessing the map.

[@GregHogg]

Agreed, that would likely be a bit faster 😊

[@mahmoud87368]

Why did't you use Counter instead of defaultdict ?

[@MagicOne18]

Counter will count every letter and there are other letters that we don't want to count as counting them will be redundant.

[@66akashagarwal]

def maxNumberOfBalloons(self, text: str) -> int:
count = Counter(text)
maxNum = 0
for i in range(len(text)//6):
for s in "balloon":
if count[s]:
count[s] -= 1
if s == "n":
maxNum += 1
else:
return maxNum
return maxNum

[@rapipo5408]

Hello Gregg, you are the best ever! thank you so much for your tutorials.
Isn't it better to remove the variable balloon and just use the string directly?
something like this:
def maxNumberOfBalloons(self, text):
counter = {'b': 0, 'a': 0, 'l': 0, 'o': 0, 'n': 0}
for c in text:
if c in 'balloon':
counter[c] += 1

return min(counter['b'], counter['a'], counter['l'] // 2, counter['o'] // 2, counter['n'])

[@Ooo0ooooO00oo]

From collections import Counter 😅

[@thefellowbreather]

Amazing! First commenter here!!