Maximum Number of Balloons

Given a string text, you want to use its characters to form as many copies of the word "balloon" as possible. Each character can be used at most once. Return the maximum number of copies. This is LeetCode 1189.

Example 1
Input: text = "nlaebolko"
Output: 1
Example 2
Input: text = "loonbalxballpoon"
Output: 2
Example 3
Input: text = "cscode"
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 has. Count them in an array of 26.

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: b, a and n as they are, l / 2 and o / 2. The answer is the smallest of these five numbers, because every copy needs all of the letters.

Walkthrough

text = "loonbalxballpoon".

LetterCount in textNeeded per copyCopies it allows
b212
a212
l422
o422
n212

The minimum is 2.

Java Solution

Integer division by 2 rounds down, which is exactly what is needed for the doubled letters.

Java
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, MaximumNumberOfBalloons.java, is on GitHub.

Complexity

  • Time: O(n): one pass to count.
  • Space: O(1): 26 counters.

Counting letters to compare two strings is the core of Valid Anagram too.