LeetCode 1189. Maximum Number of Balloons

Description

https://leetcode.com/problems/maximum-number-of-balloons/

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.

Example 1:

Input: text = "nlaebolko"
Output: 1

Example 2:

Input: text = "loonbalxballpoon"
Output: 2

Example 3:

Input: text = "leetcode"
Output: 0

Constraints:

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

Explanation

Count characters occurrences and check how many times the word of “balloon” can be formed.

Python Solution

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        
        counter = {}
        
        for c in text:
            counter[c] = counter.get(c, 0) + 1
        
        
        count = 0
        
        stop = False
        while not stop:
            
            is_finish = True
            for c in "balloon":
                counter[c] = counter.get(c, 0) - 1
                            
                if counter[c] < 0:
                    stop = True
                    is_finish = False
                    break
            
            if is_finish:         
                count += 1
                
        
        return count
            
  • Time Complexity: O(N).
  • Space Complexity: O(1).

Leave a Reply

Your email address will not be published.