Maximum Number of Balloons

Problem Summary

• Given input and target strings
• How many copies of target word ("balloon") can be made
• Duplicate of Rearrange Characters to Make Target String

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Strings
• Hash Map

Time & Space Complexity

• Time: $O(n+m)$ → Reason: Iterating through both strings once
• Space: $O(1)$ → Reason: Storing counts of 26 chars of the alphabet

Code

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        countActual = {}
        for c in text:
            countActual[c] = countActual.get(c, 0) + 1
        
        target = "balloon"
        countNeeded = {}
        for c in target:
            countNeeded[c] = countNeeded.get(c, 0) + 1

        result = []
        for c in target:
            if c not in countActual:
                return 0
            result.append(countActual[c] // countNeeded[c])
        
        return min(result)