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

Please check my playlists for free DSA problem solutions:

My Favorite Courses:

Data Structures & Algorithms:

Python:

Web Dev / Full Stack:

Cloud Development:

Game Development:

SQL & Data Science:

Machine Learning & AI:

[GregHogg]

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

[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)

[swiftlyr]

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

[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

[JoeTan-nqfq]

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.

[jdratlif]

I find your solution slightly verbose.

class Solution:
def maxNumberOfBalloons(self, text: str) -> int:
count = {'b': 0, 'a': 0, 'l': 0, 'o': 0, 'n': 0}

for c in text:
if c in count:
count[c] += 1

count['l'] //= 2
count['o'] //= 2

return min(count[letter] for letter in count)

[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.

[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

[rapipo]

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'])

[akashagarwal]

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

[mahmoud]

Why did't you use Counter instead of defaultdict ?