1189. Maximum Number of Balloons

EasyHash TableStringCounting
Leetcode Link

Problem Description

The problem provides us with a string named text and expects us to find out how many instances of the word "balloon" can be formed using the characters from text. Each character in text can be used only once, therefore it controls how many times the word "balloon" can be assembled. One thing to note is that different characters are needed in different quantities - specifically, 'b', 'a', and 'n' appear once in "balloon", whereas 'l' and 'o' appear twice. The goal is to find the maximum number of complete "balloon" words that can be created without reusing characters.

Intuition

To determine how many times the word "balloon" can be formed, we need to count the occurrences of each character that is required to form the word within text. Bearing in mind that 'l' and 'o' are needed twice in each instance of "balloon", we must count how many times 'b', 'a', 'l', 'o', and 'n' appear in text. The approach is straightforward:

  1. Count the frequency of each character in the input text.
  2. Since 'l' and 'o' are required twice, we divide the counted occurrences of 'l' and 'o' by 2. This adjusts their counts to reflect how many full "balloon" instances they can contribute to.
  3. The number of possible "balloon" instances will then be limited by the character with the least number of usable occurrences after adjustments, as every "balloon" needs at least one of each required character.
  4. We find the minimum occurrence among the character counts for 'b', 'a', 'l', 'o', and 'n' — this gives us the maximum number of "balloon" instances that can be formed.

Using a Counter to tally the characters and performing integer division (with the >> operator which is equivalent to dividing by 2 and flooring the result) on counts of 'l' and 'o' makes the solution efficient and allows us to simply use the min function to get our answer.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Solution Approach

The implementation of the solution can be understood step by step as follows:

  1. Using Counter from collections module: Python’s Counter is a container that stores elements as dictionary keys, and their counts are stored as dictionary values. Instantiating a Counter object with the string text gives us a dictionary-like object that contains all characters as keys with their respective counts as values. This is beneficial as Counter efficiently counts the occurrences of each character in the input string text.

  2. Adjusting counts for 'l' and 'o': Since the word "balloon" contains two 'l' and two 'o' characters, we need to know how many pairs of 'l' and 'o' we have. This is done by right-shifting the count of these characters by 1 position with cnt['o'] >>= 1 and cnt['l'] >>= 1. The right shift >> operator is equivalent to performing integer division by 2 and then flooring the result, which is exactly what we need to get the pair counts for 'l' and 'o'.

  3. Finding the limiting character count: The min function is used to iterate over the counts of 'b', 'a', 'l', 'o', and 'n' in the Counter object, and to find the smallest count among them. This is because we can only form as many instances of "balloon" as the least common necessary character allows. For example, if we only have one 'b', we cannot form more than one "balloon", regardless of how many 'l's or 'o's we have.

  4. Returning the result: Finally, the minimum count found is returned which represents the maximum number of times the word "balloon" can be formed from the given text.

The algorithm is efficient primarily due to the Counter data structure, which allows O(n) tallying of characters in text. Further operations (bitwise shifts and minimum value calculation) are O(1) with respect to the distinct characters involved since the word "balloon" has a constant number of unique characters.

Overall, this implementation is concise and leverages Python's built-in features to solve the problem with minimal lines of code and in efficient time complexity.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Example Walkthrough

Let's say our input string text is "loonbalxballpoon".

  1. Count characters in text:

    • We instantiate a Counter with our text:
      • Counter will be: {'l': 3, 'o': 4, 'n': 2, 'b': 2, 'a': 2, 'x': 1, 'p': 1}
    • In "balloon", 'b' appears 1 time, 'a' appears 1 time, 'l' appears 2 times, 'o' appears 2 times, and 'n' appears 1 time.

  2. Adjust counts for 'l' and 'o':

    • We right-shift the counts for 'l' and 'o' by 1 (integer division by 2):
      • After adjustment, 'l' count is 3 >> 1 = 1 and 'o' count is 4 >> 1 = 2 (>> is bit shift to the right which is equivalent to dividing by 2 and flooring the result).

  3. Find the limiting character count:

    • Using the counts we have for 'b', 'a', 'l', 'o', and 'n':
      • 'b' count is 2
      • 'a' count is 2
      • 'l' adjusted count is 1 (from the step above)
      • 'o' adjusted count is 2 (from the step above)
      • 'n' count is 2
    • The character that limits the number of possible "balloon" words is 'l', with an adjusted count of 1.

  4. Final result:

    • Since the adjusted 'l' count is 1, we can only form the word "balloon" one time from the input text.

This example helps to illustrate how the use of Counter, bit shifts, and finding the minimum count among necessary characters enables us to efficiently solve the problem and determine the maximum number of times the word "balloon" can be created from a given string of text.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def maxNumberOfBalloons(self, text: str) -> int:
5        # Create a counter from the characters in the text
6        character_count = Counter(text)
7      
8        # The letters 'o' and 'l' appear twice in "balloon", so divide their counts by 2
9        character_count['o'] //= 2
10        character_count['l'] //= 2
11      
12        # Return the minimum count among the letters in the word "balloon"
13        # Since 'balloon' has the characters 'b', 'a', 'l' (now halved), 'o' (halved), and 'n'
14        return min(character_count[char] for char in 'balon')
15
1class Solution {
2    public int maxNumberOfBalloons(String text) {
3        // Initialize an array to count the frequency of each character in the given text
4        int[] charFrequency = new int[26];
5      
6        // Iterate through each character in the text and increment the count in the array
7        for (int i = 0; i < text.length(); ++i) {
8            ++charFrequency[text.charAt(i) - 'a'];
9        }
10      
11        // Since 'l' and 'o' appear twice in "balloon", divide their counts by 2
12        charFrequency['l' - 'a'] >>= 1; // Equivalent to dividing by 2 using bitwise operator
13        charFrequency['o' - 'a'] >>= 1; // Equivalent to dividing by 2 using bitwise operator
14      
15        // Initialize the answer with a large number
16        int maxBalloons = Integer.MAX_VALUE;
17      
18        // Iterate over the characters of the word "balloon"
19        for (char c : "balon".toCharArray()) {
20            // Find the minimum frequency among the characters 'b', 'a', 'l', 'o', 'n'
21            maxBalloons = Math.min(maxBalloons, charFrequency[c - 'a']);
22        }
23      
24        // The minimum frequency determines the maximum number of "balloon" strings that can be formed
25        return maxBalloons;
26    }
27}
28
1#include <algorithm>  // For using the std::min function
2#include <string>
3using namespace std;
4
5class Solution {
6public:
7    int maxNumberOfBalloons(string text) {
8        int charCounts[26] = {}; // Initialize an array to store the counts of each letter
9
10        // Count the frequency of each character in the text
11        for (char c : text) {
12            ++charCounts[c - 'a'];
13        }
14
15        // Since 'l' and 'o' are counted twice in "balloon", we need to halve their counts
16        charCounts['o' - 'a'] /= 2;
17        charCounts['l' - 'a'] /= 2;
18
19        // Set the initial answer to a very high value
20        int minBalloons = INT_MAX;
21
22        // "balon" represents the unique characters in "balloon"
23        string balloon = "balon";
24        for (char c : balloon) {
25            // Find the minimum count of the letters in "balon" to determine the answer
26            minBalloons = min(minBalloons, charCounts[c - 'a']);
27        }
28
29        return minBalloons; // Return the minimum number of "balloon" strings
30    }
31};
32
1function maxNumberOfBalloons(text: string): number {
2    // Create an array to keep the count of each letter in the English alphabet initialized with zeroes.
3    const charCount = new Array(26).fill(0);
4
5    // Iterate through the given text and increment the count of each letter.
6    for (const char of text) {
7        charCount[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
8    }
9
10    // Calculate the maximum number of times the word "balloon" can be formed.
11    // For the letters 'l' and 'o', we should divide the count by 2 as they appear twice in the word "balloon".
12    // 'b' is at index 1, 'a' is at index 0, 'l' is at index 11, 'o' is at index 14, and 'n' is at index 13.
13    const maxBalloons = Math.min(
14        charCount['b'.charCodeAt(0) - 'a'.charCodeAt(0)],  // Count of 'b'
15        charCount['a'.charCodeAt(0) - 'a'.charCodeAt(0)],  // Count of 'a'
16        charCount['l'.charCodeAt(0) - 'a'.charCodeAt(0)] >> 1, // Count of 'l' divided by 2
17        charCount['o'.charCodeAt(0) - 'a'.charCodeAt(0)] >> 1,  // Count of 'o' divided by 2
18        charCount['n'.charCodeAt(0) - 'a'.charCodeAt(0)]    // Count of 'n'
19    );
20
21    // Return the maximum number of "balloon" strings that can be formed.
22    return maxBalloons;
23}
24
Not Sure What to Study? Take the 2-min Quiz：

Which of the following uses divide and conquer strategy?

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the string text. This is because the code iterates over each character in the string once to construct the Counter object, which is an operation that takes O(n) time. After that, the operations that halve the counts for 'o' and 'l' and the minimum finding operation take constant time, since they don't depend on the size of the input string; they only iterate over the fixed set of characters in the string 'balon'.

The space complexity of the code is also O(n). Although there are a fixed number of keys ('b', 'a', 'l', 'o', 'n') in the counter that could suggest constant space, in the worst case, the Counter might store every unique character in the input string if text does not contain any characters from "balloon". Therefore, the space used by the Counter object scales with the size of the text.

Note that these analyses assume typical implementations of Python's Counter and looping constructs.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer techniques do you use to check if a string is a palindrome?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫