Maximum Number of Balloons
Given a string text
Example 1
Output: 1
Example 2
Output: 2
Example 3
Output: 0
Explanation: there is no b, so not even one copy is possible.
How to Think About It
Step 1: Count the letters
Order does not matter, only how many of each letter text
Step 2: What one copy needs
"balloon" uses one b, one a, two l's, two o's and one n.
Step 3: The scarcest letter decides
For each letter, the number of copies it can support is its count divided by how many one copy needs: banl / 2o / 2
Walkthrough
text = "loonbalxballpoon"
| Letter | Count in text | Needed per copy | Copies it allows |
|---|---|---|---|
| b | 2 | 1 | 2 |
| a | 2 | 1 | 2 |
| l | 4 | 2 | 2 |
| o | 4 | 2 | 2 |
| n | 2 | 1 | 2 |
The minimum is 2.
Java Solution
Integer division by 2 rounds down, which is exactly what is needed for the doubled letters.
public class MaximumNumberOfBalloons {
public static int maxNumberOfBalloons(String text) {
int[] count = new int[26];
for (char c : text.toCharArray()) {
count[c - 'a']++;
}
int b = count['b' - 'a'];
int a = count['a' - 'a'];
int l = count['l' - 'a'] / 2; // "balloon" needs two l's
int o = count['o' - 'a'] / 2; // and two o's
int n = count['n' - 'a'];
return Math.min(Math.min(b, a), Math.min(Math.min(l, o), n));
}
public static void main(String[] args) {
System.out.println(maxNumberOfBalloons("nlaebolko")); // 1
System.out.println(maxNumberOfBalloons("loonbalxballpoon")); // 2
System.out.println(maxNumberOfBalloons("cscode")); // 0
}
}
The original implementation,
Complexity
- Time: O(n): one pass to count.
- Space: O(1): 26 counters.
Counting letters to compare two strings is the core of