Leetcode - Maximum Number of Balloons

Question

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. Return the maximum number of instances that can be formed.

This is a tesla question

Ideas

• Counting letters implies hash map
• We can use letters as “currency”, where we build a map of letters → frequency, and then loop over the string “balloon” first checking if any letters in our store are 0, then subtracting 1 from store[key] at each iteration and incrementing res by 1
• If any store is 1, then we return res
• We use a linear scan here 1x for our string to build the map O(n), then looping over balloon is O(len(balloon))
• One edge case here, is if you don’t have enough letters to spell balloon, you will infinitely loop, so we need to check if len(store) < 5 and return 0
• O(n)

Solution