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 only use each character in text once. Return the maximum number of instances that can be formed.

Clarifying Questions

1. Input Constraints:
   • What is the length range of the input string text?
     • The length can be up to 10^4.
2. Character Constraints:
   • Can the input string text contain characters other than lowercase English letters?
     • No, the input string will only contain lowercase English letters.
3. Output Expectations:
   • Should the function return just the count, or do we need to print each instance as well?
     • The function should return just the count of the maximum number of “balloon” instances.

Strategy

1. Frequency Count:
   • Count the frequency of each letter in the string.
2. Check “balloon” Requirements:
   • The word “balloon” consists of the characters: b, a, l, l, o, o, n.
   • From the frequency count:
     • One ‘b’
     • One ‘a’
     • Two ‘l’s
     • Two ‘o’s
     • One ‘n’
3. Determine the Maximum Instances:
   • Using the frequency dictionary, determine the limiting character — the one which has the least occurrence compared to its required frequency.

Code

#include <iostream>
#include <unordered_map>
#include <string>
#include <algorithm>

int maxNumberOfBalloons(const std::string& text) {
    std::unordered_map<char, int> char_count;
    
    // Count frequency of each character in the text
    for (char ch : text) {
        char_count[ch]++;
    }
    
    // Calculate the maximum number of "balloon"
    int b_count = char_count['b'];
    int a_count = char_count['a'];
    int l_count = char_count['l'] / 2;
    int o_count = char_count['o'] / 2;
    int n_count = char_count['n'];
    
    // Minimum of these counts will be the answer
    return std::min({b_count, a_count, l_count, o_count, n_count});
}

int main() {
    std::string text = "nlaebolko";
    std::cout << "Maximum number of 'balloon' instances: " << maxNumberOfBalloons(text) << std::endl;
    return 0;
}

Time Complexity

• O(n): Where n is the length of the string. This is because we only need to traverse the string once to count the frequencies of the characters.

Explanation

• Firstly, we traverse through the string and count the occurrence of each character using a hashmap (unordered_map).
• Then, we calculate how many times we can form the word “balloon” by considering the required frequency of each character.
• Finally, return the smallest count obtained, since that will be the limiting factor for forming the word “balloon”.

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?