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.
Input: text = "nlaebolko"
Output: 1
Explanation: using the characters from "nlaebolko" we can form one instance of "balloon" using the highlighted letters.
Input: text = "loonbalxballpoon"
Output: 2
Explanation: using the letters from text, we can form two instances of "balloon" word.
Input: text = "cscode"
Output: 0
Explanation: we cannot form "balloon" word using the letters from text "cscode".
Contents
- Solution 1 - store mapping of each letter to number of times it appeared into a HashMap
- Solution 2 - store mapping of each letter to number of times it appeared into an array
In this approach, we are going to store letters in text and their count of how many times it appeared, into a HashMap.
(For efficiency, we can consider only the letters that we are interested in 'b', 'a', 'l', 'o' and 'n').
Then, check how many sets of 'balloon' letters are present (Note: for letter 'l' and 'o' there are two needed in each instance of 'balloon') and if any letter
is missing then we will return 0.
import java.util.HashMap;
public class MaximumNumberOfBalloons {
/* Using a HashMap to store mapping of letters to number of times it appeared, then find how many instances
of 'balloon' word can be formed */
static int usingHashMapToStoreMapping(String text) {
HashMap<Character, Integer> mapping = new HashMap<>();
for(char c : text.toCharArray()){
if(c == 'b' || c == 'a' || c =='l' || c =='o' || c == 'n') {
mapping.merge(c, 1, Integer::sum);
}
}
char[] balloon = {'b', 'a', 'l', 'o', 'n'};
int max =Integer.MAX_VALUE;
for(char c: balloon) {
Integer count = mapping.get(c);
if(count == null) {
return 0;
}
if(c == 'l' || c == 'o') {
// since two l and o letters are needed, we will check for 2's count
count = count /2;
}
if(count < max) {
max = count;
}
}
return max;
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n) time where n is the input string text length.
Space complexity: O(1) since we are only storing at most 26 letters of alphabets.
Similar to above approach, instead of using a HashMap, we can store letter to its count of how many times it appeared in text into an array
of fixed size 26 (alphabets).
import java.util.HashMap;
public class MaximumNumberOfBalloons {
/* Store mapping of letter to its count into an array */
static int usingArrayToStoreMapping(String text) {
int[] mapping = new int[26];
for(char c : text.toCharArray()){
mapping[c-'a'] +=1;
}
char[] balloon = {'b', 'a', 'l', 'o', 'n'};
int max =Integer.MAX_VALUE;
for(char c: balloon) {
int count = mapping[c-'a'];
if(count == 0) {
return 0;
}
if(c == 'l' || c == 'o') {
// since two l and o letters are needed, we will check for 2's count
count = count /2;
}
if(count < max) {
max = count;
}
}
return max;
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n) time where n is the input string text length.
Space complexity: O(1) since we are only storing at most 26 letters of alphabets.
Above implementations source code can be found at
GitHub link for Java code