Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Problem 3: Maximum Number of Balloons (easy)

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:

.....

.....

.....

Like the course? Get enrolled and start learning!
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

from collections import Counter

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        min_count = float('inf')

        balloon_counter = Counter('balloon')    
        text_counter = Counter(text)

        for char, freq in balloon_counter.items():
            if char not in text_counter:
                return 0
            else:
                min_count = min(min_count, text_counter[char] // freq)

        return min_count
P

Pete Stenger

· 2 years ago

        c = Counter(text)

        min_count = min([c.get('b', 0), c.get('a', 0), c.get('l', 0) // 2, c.get('o', 0) // 2, c.get('n', 0)])
        return min_count
D

designgurus

· a year ago

The solution code is HORRENDOUS! why would you literally hardcode all 5 lines?

class Solution:
def maxNumberOfBalloons(self, text: str) -> int:
charFreq = Counter(text)
word = 'balloon'
wordCharFreq = Counter(word)
result = sys.maxsize

for char in set(word):
result = min(result, charFreq[char] // wordCharFreq[char])

return result
Modestas Filipavicius

Modestas Filipavicius

· 7 months ago

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        target = 'balloon'
        min_count = 0
        
        # count all chars in text
        ct = {}
        for char in text:
            ct[char] = ct.get(char, 0) + 1

        # traverse target word multiple times
        # until counts dict is depleted
        while True:
            for char in target:
                char_c = ct.get(char, 0)
                print(f'char: {char}, count: {char_c}')
                # stop condition
                if char_c == 0:
                    return min_count
                # decrement target char count
                ct[char] = char_c - 1
            # whole traversal of target word, increment min_count
            min_count += 1
        return min_count


``