Blogs Hub

Maximum Number of Balloons - MiniTV

Maximum Number of Balloons - मिनी टीवी

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.

 

Example 1:

Input: text = "nlaebolko"

Output: 1

 

Example 2:

Input: text = "loonbalxballpoon"

Output: 2

 

Example 3:

Input: text = "leetcode"

Output: 0

 

Constraints:

1 <= text.length <= 10^4

text consists of lower case English letters only.

 

Solution:

using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode.AskGif.Easy.String
{
    class MaxNumberOfBalloonsSln
    {
        public void execute()
        {
            var res = MaxNumberOfBalloons("leetcode");
        }

        public int MaxNumberOfBalloons(string text)
        {
            var dict = new Dictionary<char, int>();
            char[] word = new char[] {'b', 'a', 'l', 'l', 'o', 'o', 'n' };
            foreach (var ch in text)
            {
                if(dict.ContainsKey(ch))
                {
                    dict[ch]++;
                }
                else
                {
                    dict[ch] = 1;
                }
            }

            int min = Int16.MaxValue;

            //since l and o appear twice, lets divide it by two in dictionary if they exists
            if(dict.ContainsKey('l'))
                dict['l'] = dict['l'] / 2;
            if (dict.ContainsKey('o'))
                dict['o'] = dict['o'] / 2;

            foreach (var ch in word)
            {
                if (dict.ContainsKey(ch))
                {
                    if(dict[ch]<min)
                    {
                        min = dict[ch];
                    }
                }
                else
                {
                    return 0;
                }
            }

            return min;
        }
    }
}

Time Complexity: O(n)

Space Complexity: O(n)