Using the letters of a text, at most once each, how many times can you form the word balloon?
DSA Animator › DSA Revision › Strings › Maximum Number of Balloons
Remember: how many words can I build means the scarcest letter decides. Divide by how many times the word needs each letter. The video solves Maximum Number of Balloons (LeetCode 1189, Easy) with the Frequency Count pattern from the Strings topic, and you can replay every step in the interactive Maximum Number of Balloons animation.
Using the letters of a text, at most once each, how many times can you form the word balloon?
For loon bal x ball poon, you can form balloon 2 times.
Building the word over and over, and removing letters each time, is slow and messy. Counting the letters answers it directly.
Count each letter of the text. Balloon needs one b, one a, two l, two o and one n. So divide the counts of l and o by 2, and the answer is the smallest result.
The counts are b 2, a 2, l 4, o 4 and n 2. b gives 2, and a gives 2. l gives 4 divided by 2, which is 2, and o also gives 2. n gives 2. The smallest of these is 2, so the answer is 2.
In code, count all 26 letters. Return the minimum of b, a, l divided by 2, o divided by 2, and n. That's O of n time and O of 1 space.
Remember: how many words can I build means the scarcest letter decides. Divide by how many times the word needs each letter.