1189. 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 <= 104
• text consists of lower case English letters only.

題目翻譯

題目很簡單，就是會給一個字串參數 text，需要在這個字串中的所有 char，每次只能操作一個 char 的情況下，找出可以排出多少次 balloon。

解法解析

這題算是 Easy 的題目，很簡單的解法是。單純的使用迴圈去遍歷 text 的所有 char。找出數量最少的 char，其中要注意的是 l 和 o。這兩個 char 會需要比其他多一倍才行。最好的情況下： Time Complexity：O(n) Space Complexity：O(1)

可以看到以下的範例，基本上的解法就是使用一個 Hash Map 去判斷，並且計算數量。 最後回傳最小數量的數值，做為答案。

程式範例

Python

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        counter = {
            "b": 0,
            "a": 0,
            "l": 0,
            "o": 0,
            "n": 0
        }
        for char in text:
            if char in counter:
                counter[char] += 1 if char in ('l', 'o') else 2

        return min(counter.values()) // 2

JavaScript

/**
 * @param {string} text
 * @return {number}
 */
var maxNumberOfBalloons = function (text) {
    const counter = {
        b: 0,
        a: 0,
        l: 0,
        o: 0,
        n: 0,
    };
    const doubleChar = new Set(['l', 'o']);
    for (let char of text) {
        if (char in counter) {
            counter[char] += doubleChar.has(char) ? 1 : 2;
        }
    }

    return Math.floor(Math.min(...Object.values(counter)) / 2);
};

Go

func maxNumberOfBalloons(text string) int {
    letterCnt := make(map[rune]int)

    for _, rn := range text {
        letterCnt[rn]++
    }

    letterCnt['l'] /= 2
    letterCnt['o'] /= 2

    output := math.MaxInt32
    for _, rn := range "balon" {
        if letterCnt[rn] < output {
            output = letterCnt[rn]
        }
    }

    return output
}

Swift

class Solution {
    fun maxNumberOfBalloons(text: String): Int {
        val balloon = IntArray(5)

        for(i in 0 until text.length) {
            val char = text[i]

            when(char) {
                'b' -> balloon[0] += 2
                'a' -> balloon[1] += 2
                'l' -> balloon[2] += 1
                'o' -> balloon[3] += 1
                'n' -> balloon[4] += 2
            }
        }

        return balloon.min()!! / 2
    }
}

Kotlin

class Solution {
    func maxNumberOfBalloons(_ text: String) -> Int {
        var lettersNeeded:[Character: Int] = ["b": 0, "a": 0, "l": 0, "o": 0, "n" : 0]

        for char in text {
            if lettersNeeded[char] != nil {
               lettersNeeded[char]! += 1
            }
        }

        var singleLetterCount = min(lettersNeeded["b"]!, lettersNeeded["a"]!, lettersNeeded["n"]!)
        var doubleLetterCount = min(lettersNeeded["o"]!, lettersNeeded["l"]!)

        if singleLetterCount == 0 || doubleLetterCount == 0 {
            return 0
        } else {
            return doubleLetterCount/2 < singleLetterCount ? doubleLetterCount/2 : singleLetterCount
        }
    }
}