algoadvance

Leetcode 1189. Maximum Number of Balloons

Problem Statement

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.

Clarifying Questions

1. Input Constraints: What is the maximum length of the input string text?
   • Assume 1 <= text.length <= 10^4.
2. Case Sensitivity: Is the input string case-sensitive?
   • It’s typically considered case-sensitive unless specified otherwise. Assume it is case-sensitive.
3. Characters in Text: Should we consider any characters outside the ones in “balloon”?
   • We only need to count the occurrences of characters in “balloon”.
4. Characters in Different Alphabets: Is the input string limited to English alphabets?
   • The problem implies using standard English alphabets by forming the word “balloon”.

Strategy

1. Character Frequency: Count the frequency of each character in the string text.
2. Frequency Requirement: The word “balloon” consists of the characters:
   • ‘b’, ‘a’, ‘l’ (x2), ‘o’ (x2), ‘n’

   Therefore, we need:

   • 1 ‘b’
   • 1 ‘a’
   • 2 ‘l’
   • 2 ‘o’
   • 1 ‘n’

3. Form Instances: Determine the limiting factor by calculating how many times we can extract “balloon” from our character counts. For each required character, calculate how many times it can contribute to forming “balloon”.

4. Minimum Ratio: Take the minimum of these calculated values to determine the maximum number of “balloon” instances that can be formed.

Code

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int maxNumberOfBalloons(String text) {
        Map<Character, Integer> charCount = new HashMap<>();
        
        // Count frequency of each character in text
        for (char c : text.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }
        
        // Required frequency for each character in "balloon"
        int bCount = charCount.getOrDefault('b', 0);
        int aCount = charCount.getOrDefault('a', 0);
        int lCount = charCount.getOrDefault('l', 0);
        int oCount = charCount.getOrDefault('o', 0);
        int nCount = charCount.getOrDefault('n', 0);
        
        // Calculate the maximum number of "balloon" instances
        int maxBalloons = Integer.MAX_VALUE;
        maxBalloons = Math.min(maxBalloons, bCount);
        maxBalloons = Math.min(maxBalloons, aCount);
        maxBalloons = Math.min(maxBalloons, lCount / 2);
        maxBalloons = Math.min(maxBalloons, oCount / 2);
        maxBalloons = Math.min(maxBalloons, nCount);
        
        return maxBalloons;
    }
}

Time Complexity

• Character Counting: The first loop iterates over the string text, giving a time complexity of (O(n)) where (n) is the length of the string.
• Retrieving Counts & Calculating Minimum: The operations of retrieving counts and calculating the minimum are performed a constant number of times (specifically, five times for ‘b’, ‘a’, ‘l’, ‘o’, ‘n’ in this case), resulting in (O(1)).

Thus, the overall time complexity is (O(n)), which is efficient for the given constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?