1189. Maximum Number of Balloons - LeetCode Fastest Solution

Hello Code Recipian! Welcome back to another article on  leetcode problem solutions. Today we will be solving leetcode problem 1189. Maximum Number of Balloons.

Problem Statement: Maximum Number of Balloons

Given a input string text, use the characters of text to form as many instances of the word "balloon" as possible.

You are only allowed to use each character at most once. Return the maximum number of times "balloon" can be formed.

Example 1:

Input: text = "nlaebolko"
Output: 1
Explanation: nlaebolko

Example 2:

Input: text = "loonbalxballpoon"
Output: 2
Explanation: loonbalxballpoon

Example 3:

Input: text = "leetcode"
Output: 0

Constraints:

• 1 <= text.length <= 10^4

• text consists of only lower case English letters.

Solution

We can use the hashmap to efficiently solve this problem in linear time. The idea is to count the frequency of characters in input string and using this character count determine how many times the word "balloon" can be formed. Let's see how this works in detail.

Algorithm

Below is a step-by-step explanation for the working of the algorithm:

1. Initialization:

   To begin with, initialize a hashmap charCount that takes a character key and an integer value. This hashmap is used for counting the frequency of each character in the input string.

2. Count characters:

   Iterate through the characters of the input string text from start to end. In each iteration we increment the current character count by one.

3. Count instances of balloon:

   Next step is to use the frequencies we got in the previous step, to calculate how many times we can form the word "balloon". To get this we perform the following steps:

   1. Initialize result variable:

      Initialize a variable minCharCount, this is our result variable, this should be initially set to some max value.

   2. Normalize charCount for 'l' and 'o':

      Since characters 'l' and 'o' appear two times in the word "balloon", we divide 'l' and 'o' by 2 to normalize it. This division would mean, now we need a single occurrence of the letters 'b', 'a', 'l', 'o' and 'n' in order to form one instance of the word "balloon". This division is done in order to make our calculation simpler for the next steps.

   3. Calculate maximum no. of instances of balloon:

      Next in order to get the final result, we have to find the minimum of the charCount among 'b', 'a', 'l', 'o' and 'n'. The intuition behind this is that, in order to form the word balloon we need 'b', 'a', 'l', 'o' and 'n' to be present at least one time each.

      
      

      For forming 1 instance of balloon, we need 1 'b', 1 'a', 2 'l', 2 'o' and 1 'n'. But, since we have divided 'l' and 'o' by 2, we need just 1 occurrence even for 'o' and 'l'. Therefore for forming once instance of balloon we need 1 occurrence of 'b', 'a', 'l', 'o' and 'n'. For forming two instances of balloon we need 2 occurrences of 'b', 'a', 'l', 'o' and 'n'. Even if one of the these letters has count = 1 we can only form one instance of balloon.

      That is the idea behind taking minimum of character counts. The maximum number of instances of balloon that can be formed depends on the minimum of the frequencies among 'b', 'a', 'l', 'o' or 'n'.

4. Return result:

   Finally we return the minCharCount as result.

Simulation

Below is a pictorial depiction of the working of the algorithm:

Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses:

1. Udemy Video Tutorials - Available at 95% off

2. System Design Interview Complete Guide

3. Cracking The Coding Interview - Most Preferred Book For Coding Interviews

4. Data Structures And Algorithms - A Complete Guide 

5. Learn In-Demand Tech Skills And Stay Ahead Of Others

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

TypeScript Solution

C++ Solution

C# Solution

C Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Rust Solution

Scala Solution

Complexity Analysis

Time Complexity

Time complexity of this solution is O(n), where n is the length of string text. This is because we iterate each character of text for counting the frequency of characters. Apart from this all are constant time operations.

Space Complexity

Even though we use a hashmap for storing the character count, as per the problem constraints text can only have lower case English letters. Therefore, in the worst case the maximum number of elements that the hashmap can have is 26. Hence the space complexity is O(26) which in general can be represented as O(1).

That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries.

If you enjoyed this article, please subscribe to our website and Youtube channel. Your support inspires us to create more such articles in the future.

Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section. There's a wealth of knowledge waiting for you there!

Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.

Follow us: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.