easy Problem 3 Maximum Number of Balloons

Problem Statement

Given a string, determine the maximum number of times the word "balloon" can be formed using the characters from the string. Each character in the string can be used only once.

Examples:

1. Example 1:

   • Input: "balloonballoon"
   • Expected Output: 2
   • Justification: The word "balloon" can be formed twice from the given string.

2. Example 2:

   • Input: "bbaall"
   • Expected Output: 0
   • Justification: The word "balloon" cannot be formed from the given string as we are missing the character 'o' twice.

3. Example 3:

   • Input: "balloonballoooon"
   • Expected Output: 2
   • Justification: The word "balloon" can be formed twice, even though there are extra 'o' characters.

Constraints:

• 1 <= text.length <= 10⁴
• text consists of lower case English letters only.

Solution

To solve this problem, you start by creating a hashmap to count the frequency of each letter in the given string. Since the word "balloon" contains specific letters with varying frequencies (like 'l' and 'o' appearing twice), you need to account for these in your hashmap. Once you have the frequency of each letter, the next step is to determine how many times you can form the word "balloon". This is done by finding the minimum number of times each letter in "balloon" appears in the hashmap. The limiting factor will be the letter with the minimum frequency ratio to its requirement in the word "balloon". This approach ensures a balance between utilizing the available letters and adhering to the letter composition of "balloon".

1. Character Frequency Count: Traverse the string and populate a hashmap with the frequency count of each character.

2. Determine Maximum Count: Check the hashmap to determine the maximum number of times the word "balloon" can be formed. For characters 'b', 'a', and 'n', their frequency in the hashmap directly gives the number of times they can be used. For 'l' and 'o', we need to divide their frequency by 2.

3. Result Calculation: The minimum value among the counts of 'b', 'a', 'l'/2, 'o'/2, and 'n' will give the maximum number of times the word "balloon" can be formed.

4. Return the Result: Return the calculated minimum value as the final result.

This approach is effective because it ensures that we account for the frequency of each character required to form the word "balloon". Using a hashmap allows for efficient storage and retrieval of character frequencies.

The general pattern — multiset cover count. This is the "how many copies of a target multiset can I build from a source multiset" problem. The answer is:

max copies = min over each needed character c of ⌊ have[c] / need[c] ⌋

For "balloon", need = {b:1, a:1, l:2, o:2, n:1}, so the count is min(⌊have[b]/1⌋, ⌊have[a]/1⌋, ⌊have[l]/2⌋, ⌊have[o]/2⌋, ⌊have[n]/1⌋). Ransom Note (LC383) is the k = 1 boolean special case — you only ask "can I build the target at least once?", i.e. whether have[c] ≥ need[c] for every c; this problem is the general max-k version.

Algorithm Walkthrough:

Given the input string "balloonballoooon":

• Initialize an empty hashmap.
• Traverse the string and populate the hashmap with character frequencies: {'b':2, 'a':2, 'l':4, 'o':6, 'n':2}.
• Calculate the maximum number of times "balloon" can be formed:
  • 'b' can be used 2 times.
  • 'a' can be used 2 times.
  • 'l' can be used 4/2 = 2 times.
  • 'o' can be used 6/2 = 3 times.
  • 'n' can be used 2 times.
• The minimum among these values is 2 — the limiting letters are 'b', 'a', and 'n' (each available only twice), while 'l' (2) and 'o' (3) are in surplus. So "balloon" can be formed 2 times.

Here is the visual representation of the algorithm:

Code

Here is the code for this algorithm:

import java.util.HashMap;

public class Solution {

  public int maxNumberOfBalloons(String text) {
    // Create a hashmap to store character frequencies
    HashMap<Character, Integer> charCount = new HashMap<>();

    // Populate the hashmap with character frequencies from the string
    for (char c : text.toCharArray()) {
      charCount.put(c, charCount.getOrDefault(c, 0) + 1);
    }

    int minCount = Integer.MAX_VALUE;
    // Calculate the maximum number of times "balloon" can be formed
    minCount = Math.min(minCount, charCount.getOrDefault('b', 0));
    minCount = Math.min(minCount, charCount.getOrDefault('a', 0));
    minCount = Math.min(minCount, charCount.getOrDefault('l', 0) / 2);
    minCount = Math.min(minCount, charCount.getOrDefault('o', 0) / 2);
    minCount = Math.min(minCount, charCount.getOrDefault('n', 0));

    return minCount;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(sol.maxNumberOfBalloons("balloonballoon")); // Expected: 2
    System.out.println(sol.maxNumberOfBalloons("bbaall")); // Expected: 0
    System.out.println(sol.maxNumberOfBalloons("balloonballoooon")); // Expected: 2
  }
}

Complexity Analysis

Time Complexity: The algorithm traverses the string once to populate the hashmap, which is O(n), where n is the length of the string. The subsequent operations are constant time. Therefore, the overall time complexity is O(n).

Space Complexity: The space complexity is determined by the hashmap, which in the worst case will have an entry for each unique character in the string. However, since the English alphabet has a fixed number of characters, the space complexity is O(1).

🎯 STRICT STANDOUT: Why / worked+complexity / pattern+when-not / edge / drills — Solution Maximum Number of Balloons

Why this concept exists (judgment layer)

Solution counts and mins divisions — correct. Elevation makes need-array explicit and ties to ransom-note / construct-string family.

Worked example with complexity derivation

Count text; ans = min(b, a, l//2, o//2, n).
nlaebolko → 1; loonbalxballpoon → 2.
Θ(n) scan; O(1) space int[26].
Bug class: using min of raw l,o without /2 over-counts.

Pattern + when-NOT / named alternative

PATTERN: multiset cover count for repeated target. WHEN NOT: form any permutation subsequence with order — different. If letters cannot be reused across copies — already modeled by division.

Edge case / failure mode

Hand-run ""→0; "balloonballoon"→2; "balon"→0 (need 2 l). Non-balloon letters ignored.

Hostile-panel drills (defend the decision)

Q1. Write the min expression.
Model answer: min(cnt[b], cnt[a], cnt[l]/2, cnt[o]/2, cnt[n]).

Q2. Link to Ransom Note.
Model answer: Ransom is boolean: for all c, magazine[c]≥note[c]; balloon is max k s.t. k·need ≤ source.

Q3. If target were 'ball'?
Model answer: min(b,a,l/2) — only letters in target matter.