Maximum Number of Balloons Leetcode Solution

Problem Statement

In this problem, we are given a string of characters containing lower-case English letters. We need to find how many instances of the word “balloon” can we make using the characters of the given string.

Example

String = "banooll"

1

Explanation:

String = baqwweeeertylln

0

Explanation: As the string doesn’t have any ‘o’, we can not make even a single instance of “balloon”. So, we print 0.

Approach

It is obvious that we need to know the frequency of letters in the string which makes the word “balloon”. That is, it is only important for us to save the frequencies of letters ‘b’, ‘a’, ‘l’, ‘o’ and ‘n’ as they constitute the string “balloon”. Then, we can find the letter having the minimum count to decide the number of instances of the word possible. This is a typical example of hashing characters with their frequencies. Note that we need to consider that only half of the frequencies of the letters ‘l’ and ‘o’ can be used to make a single word. In order to generalize this case, we half the frequency of these two letters beforehand.

Algorithm

1. Initialize 5 integers: b, a, l, o, and n to store their respective frequencies as 0
2. For every character ‘chr‘ in the string:
   • If ‘chr‘ is any of the above-mentioned characters, increment its frequency
3. Divide l and o by 2
4. Return the minimum among b, a, l, o, and n
5. Print the result

Implementation of Maximum Number of Balloons Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

int maxNumberOfBalloons(string text)
{
    int b = 0 , a = 0 , l = 0 , o = 0 , n = 0;
    for(char &chr : text)
    {
        switch(chr)
        {
            case 'b' : b++;
                break;
            case 'a' : a++;
                break;
            case 'l' : l++;
                break;
            case 'o' : o++;
                break;
            case 'n' : n++;
                break;
        }
    }

    l /= 2;
    o /= 2;
    return min({b , a , l , o , n});
}

int main()
{
    string text = "blloona";
    cout << maxNumberOfBalloons(text) << '\n';
    return 0;
}

Java Program

import java.lang.*;

class max_balloons
{
    public static void main(String args[])
    {
        String text = "blloona";
        System.out.println(maxNumberOfBalloons(text));
    }

    static int maxNumberOfBalloons(String text)
    {
        int b = 0 , a = 0 , l = 0 ,  o = 0 , n = 0;
        char chr;
        for(int i = 0 ; i < text.length() ; i++)
        {
            chr = text.charAt(i);
            switch(chr)
            {
                case 'b' : b++;
                case 'a' : a++;
                case 'l' : l++;
                case 'o' : o++;
                case 'n' : n++;
                default: ;
            }
        }

        l /= 2;
        o /= 2;

        return Math.min(b , Math.min(a , Math.min(l, Math.min(o , n))));
    }
}

1

Complexity Analysis of Maximum Number of Balloons Leetcode Solution

Time Complexity

O(N) as we traverse the string once to store frequencies of certain characters. Here, N = size of the array.

Space Complexity 

O(1) as we use constant memory space irrespective of the input. We just store some variables for counting their frequencies.