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.

Examples

Example 1:

Input: text = "nlaebolko"
Output: 1

Example 2:

Input: text = "loonbalxballpoon"
Output: 2

Example 3:

Input: text = "leetcode"
Output: 0

Solution

Method 1 - Using Hashtable

We go through balloon and create frequency map. We do the same for text. Then we find the min number of multiple available, because that is the max number of balloons we can make.

public int maxNumberOfBalloons(String text) {
	String balloon = "balloon";
	
	Map<Character, Integer> map = new HashMap<>();
	balloon.chars().forEach(c -> map.put((char) c, map.getOrDefault((char) c, 0) + 1));
	
	int[] txtFreq = new int[26];
	text.chars().forEach(c -> ++txtFreq[c - 'a']);
	int ans = Integer.MAX_VALUE;

	for (char c: map.keySet()) {
		ans = Math.min(ans, txtFreq[c - 'a'] / map.get(c));
	}

	return ans;
}