[leetcode #1189] Maximum Number of Balloons

Problem

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⁴
・ text consists of lower case English letters only.

Idea

これは、指定した文字列の文字を抽出することによって、どのくらいの「風船」を作成できるかを決定する問題です.「風船」を構成する文字b,a,l,o,nの数だけ数えて、その文字の最低数を返すだけです.lとoは2つ必要なので、合計の1/2として計算します.
アルゴリズムは以下の通りです.

で与えられた文字を探索し、各文字の周波数を地図に格納する.

b、a、l、o、n文字をキーに地図上で周波数を確認します.lまたはoの場合、周波数の1/2が計算されます.

は、

の5文字の周波数値の最小値を返します.

Solution

class Solution {
    public int maxNumberOfBalloons(String text) {
        Map<Character, Integer> map = new HashMap<>();

        for (int i =0; i < text.length(); i++) {
            if (!map.containsKey(text.charAt(i))) {
                map.put(text.charAt(i), 1);
            } else {
                int val = map.get(text.charAt(i));
                map.put(text.charAt(i), val+1);
            }
        }
        String balloon = "balon";
        int res = Integer.MAX_VALUE;

        for (int i=0; i < balloon.length(); i++) {
            if (!map.containsKey(balloon.charAt(i)))
                return 0;
            if (balloon.charAt(i) == 'l' || balloon.charAt(i) == 'o') {
                res = Math.min(res, map.get(balloon.charAt(i))/2);
            } else
                res = Math.min(res, map.get(balloon.charAt(i)));
        }
        return res;
    }
}

mapを使用する必要がなく、直感的にリリースするとパフォーマンスが向上します.

class Solution {
    public int maxNumberOfBalloons(String text) {
        int bCount = 0, aCount = 0, lCount = 0, oCount = 0, nCount = 0;

        // Count the frequencey of all the five characters
        for (int i = 0; i < text.length(); i++) {
            if (text.charAt(i) == 'b') {
                bCount++;
	    } else if (text.charAt(i) == 'a') {
        	aCount++;
            } else if (text.charAt(i) == 'l') {
                lCount++;
            } else if (text.charAt(i) == 'o') {
                oCount++;
            } else if (text.charAt(i) == 'n') {
                nCount++;
            }
        }

	// Find the potential of each character.
        // Except for 'l' and 'o' the potential is equal to the frequency.
    	lCount = lCount / 2;
        oCount = oCount / 2;

        // Find the bottleneck.
        return Math.min(bCount, Math.min(aCount, Math.min(lCount, Math.min(oCount, nCount))));
    }
}

Reference

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