Problem Explanation

We are given a string of text, and using the characters of this text, we are to form as many instances of the word "balloon". Each character in the text can only be used once. The task is to find and return the maximum number of instances that can be formed.

To use as an example, consider the string text = "nlaebolko". We can form the word "balloon" once using the letters in the string, hence, the output will be 1.

Solution Approach

In order to solve this problem we will be using a frequency count system. Here, we would create a frequency table for the characters in text. Since we know that the word "balloon" can only be formed if all characters needed are present in text, we iterate through the frequency table of text and for each character in 'ban' and for each character i of 'balloon' we check if it is present in text and increment the count of instances that can be formed by one if they are. For each character i in 'lo', we check if it is present in text and double the count of instances that can be formed if they are.

Let's consider the string text: "loonbalxballpoon". The result for this example would be 2 because the word "balloon" can be formed twice from the characters in the string.

Python Solution

1
2python
3class Solution:
4    def maxNumberOfBalloons(self, text: str) -> int:
5        count = [0]*26
6        
7        # create frequency table
8        for c in text:
9            count[ord(c) - ord('a')] += 1
10
11        mini = min(count[ord('b') - ord('a')], count[ord('a') - ord('a')],
12                   count[ord('l') - ord('a')]//2, count[ord('o') - ord('a')]//2, 
13                   count[ord('n') - ord('a')])
14        return mini

Java Solution

1
2java
3class Solution {
4    public int maxNumberOfBalloons(String text) {
5        int[] count = new int[26];
6        for (int i = 0; i < text.length(); i++) {
7            count[text.charAt(i) - 'a']++;
8        }
9        int min = Math.min(count[1], count[0]); 
10        min = Math.min(min, count[11]/2);
11        min = Math.min(min, count[14]/2);
12        min = Math.min(min, count[13]);  
13        return min;
14    }
15}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int maxNumberOfBalloons(string text) {
6        vector<int> count(26, 0);
7        for (char c : text) {
8            ++count[c - 'a'];
9        }
10
11        count['l' - 'a'] /= 2;
12        count['o' - 'a'] /= 2;
13
14        string balloon = "balon";
15        int ans = text.size();
16
17        for (char c : balloon) {
18            ans = min(ans, count[c - 'a']);
19        }
20
21        return ans;
22    }
23};

JavaScript Solution

1
2javascript
3var maxNumberOfBalloons = function(text) {
4    let count = new Array(26).fill(0);
5    for(let i = 0; i < text.length; i++){
6        count[text.charCodeAt(i) - 97] += 1;
7    }
8    let min = Math.min(count[1], count[0]);
9    min = Math.min(min, Math.floor(count[11]/2));
10    min = Math.min(min, Math.floor(count[14]/2));
11    min = Math.min(min, count[13]);
12    return min;
13};

C# Solution

1
2csharp
3public class Solution {
4    public int MaxNumberOfBalloons(string text) {
5        int[] count = new int[26];
6        foreach (char c in text){
7             count[c-'a']++;
8        }
9        int min = Math.Min(count['b'-'a'], count['a'-'a']);
10        min = Math.Min(min, count['l'-'a']/2);
11        min = Math.Min(min, count['o'-'a']/2);
12        min = Math.Min(min, count['n'-'a']);
13        return min;
14    }
15}

By counting the frequency of each character in text and by checking if they match the required characters to form the word "balloon", we can calculate and return the maximum number of instances that can be formed. For each available "b", "a", "l", "l", "o", "o", "n", we may form a "balloon". And there are count['l'-'a']/2 "l"s, count['o'-'a']/2 "o"s available. There are count['b'-'a'] "b"s, count['a'-'a'] "a"s, count['n'-'a'] "n"s available, hence the possible number of "balloon"s is the minimum of these counts.# Ruby Solution

1
2ruby
3def max_number_of_balloons(text)
4    count = Array.new(26, 0)
5    text.each_char do |c|
6        count[c.ord - 97] += 1
7    end
8    min = [count[1], count[0]].min
9    min = [min, count[11]/2].min
10    min = [min, count[14]/2].min
11    min = [min, count[13]].min
12    return min
13end

By creating a frequency table for the input string, this method is able to iterate over each character in the string, compute its ASCII value and increment its corresponding index in the count array. This operation allows easy access to the frequency of each character in the string as their ASCII values are used to reference their indices in the count array.

We set an initially high minimum value and subsequently compute the minimum count for each character needed for the formation of the word "balloon" i.e., 'b', 'a', 'l' (2 'l' for each 'balloon'), 'o' (2 'o' for each 'balloon'), 'n'. We compute the minimum possible number of "balloon" formations for each character and assign the smallest number to min. After iterating through all the relevant characters, we return min.

Although Ruby is not typically considered for competitive coding, this solution follows the same logical schematic as solutions for more commonly used languages and serves to demonstrate the problem solving capabilities of Ruby. It keeps the stack trace optimized and performs well within time limits as its time complexity is O(n).