1189. Maximum Number of Balloons

Problem Description

Given a string text, determine the maximum number of times the word "balloon" can be formed using the characters from text, where each character in text can be used at most once.

Solution: Counting and Frequency Analysis

This problem can be efficiently solved using a frequency counting approach. We'll count the occurrences of each character in the input string text. Since "balloon" contains multiple instances of some letters ('l' and 'o'), we need to handle those separately.

Algorithm:

1. Character Counting: Create a dictionary (or hash map) to store the frequency of each character in text.
2. Balloon Letter Counts: Initialize counts for each letter in "balloon": 'b', 'a', 'l', 'o', 'n'. 'l' and 'o' need special treatment as they appear twice.
3. Frequency Calculation: For each letter in "balloon", find its frequency from the character count. Divide the counts for 'l' and 'o' by 2, as we need pairs of these letters for each "balloon".
4. Minimum Frequency: The maximum number of "balloons" that can be formed is limited by the letter with the lowest frequency (after handling the 'l' and 'o' counts). Find the minimum among the adjusted frequencies.

Code Implementation (Python)

from collections import Counter
 
def maxNumberOfBalloons(text: str) -> int:
    """
    Calculates the maximum number of "balloons" that can be formed from the characters in text.
 
    Args:
        text: The input string.
 
    Returns:
        The maximum number of "balloons" that can be formed.
    """
    counts = Counter(text)  # Count character frequencies
    balloon_counts = {'b': counts['b'], 'a': counts['a'], 'l': counts['l'] // 2, 'o': counts['o'] // 2, 'n': counts['n']}
    return min(balloon_counts.values()) #Find the minimum count
 
 

Time and Space Complexity Analysis

• Time Complexity: O(N), where N is the length of the input string text. This is because the character counting and the subsequent minimum frequency calculation take linear time with respect to the input size.
• Space Complexity: O(1). The space used is constant, as we only store a fixed number of character counts (the letters in "balloon"). The Counter object in Python might have a small overhead, but it's considered constant in this context because the number of unique characters is limited (26 letters in English).

Code Implementations in Other Languages

The core logic remains consistent across different languages. Here are examples in Java and C++:

Java:

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public int maxNumberOfBalloons(String text) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : text.toCharArray()) {
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }
        int[] balloonCounts = new int[] {counts.getOrDefault('b', 0), counts.getOrDefault('a', 0), 
                                          counts.getOrDefault('l', 0) / 2, counts.getOrDefault('o', 0) / 2, 
                                          counts.getOrDefault('n', 0)};
 
        int minCount = Integer.MAX_VALUE;
        for (int count : balloonCounts) {
            minCount = Math.min(minCount, count);
        }
        return minCount;
    }
}

C++:

#include <iostream>
#include <string>
#include <map>
#include <algorithm>
 
using namespace std;
 
int maxNumberOfBalloons(string text) {
    map<char, int> counts;
    for (char c : text) {
        counts[c]++;
    }
    int balloonCounts[] = {counts['b'], counts['a'], counts['l'] / 2, counts['o'] / 2, counts['n']};
    return *min_element(balloonCounts, balloonCounts + 5);
}

These code examples all follow the same fundamental approach: count characters, adjust for duplicates in "balloon", and find the minimum frequency. The choice of language primarily impacts the syntax and data structures used.