[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

주어진 string의 문자를 추출해서 "balloon"을 몇 개나 만들 수 있는지 확인하는 문제다. "balloon"을 이루고 있는 문자인 b, a, l, o, n의 수만 센 뒤 해당 문자의 최소 개수를 리턴하면 된다. l과 o는 두 개 필요하므로 합계의 1/2로 계산해야 한다.

알고리즘은 다음과 같다.

1. 주어진 문자를 탐색하며 각 문자의 빈도를 map에 저장한다.
2. b, a, l, o, n 문자를 key로 하여 map에서 빈도를 확인한다. l이나 o일 경우 빈도의 1/2로 계산한다.
3. 다섯 개 문자의 빈도 값 중 가장 작은 값을 리턴한다.

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/