Description

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:

1Input: text = "nlaebolko"
2Output: 1

Example 2:

1Input: text = "loonbalxballpoon"
2Output: 2

Example 3:

1Input: text = "leetcode"
2Output: 0

Constraints:

  • 1 <= text.length <= 10^4
  • text consists of lower case English letters only.

Solution

Based on the problem, it seems like we need to find out occurrences of each character of word balloon and check in the incoming text, how many times each of those occur. That will be the number of times we can form the word "balloon" using the given text. Here, we can use each character only once, so this will straight away give us the answer.

This problem can be generalised for any text as input and we want to verify how many times we can form a given string pattern.

Using HashMap

Again, it’s actually counting occurrences of each character of the word balloon. So, we can use HashMap here. If a particular character is needed more than one times in the pattern, we have to make sure that we have that many copies of this character in the input text.

 1class Solution {
 2    public int maxNumberOfBalloons(String text) {
 3        return maxNumberOfBalloons(text, "balloon");
 4    }
 5
 6    private int maxNumberOfBalloons(String text, String wordPattern) {
 7        Map<Character, Integer> counts = new HashMap<>();
 8        for (char c: text.toCharArray()) {
 9            counts.put(c, counts.getOrDefault(c, 0) + 1);
10        }
11        int min = Integer.MAX_VALUE;
12        // Check maximum how many times each character in wordPattern can be found in text
13        for (char c: wordPattern.toCharArray()) {
14            if (!counts.containsKey(c)) {
15                return 0;
16            }
17            int count = counts.get(c);
18            if (c == 'l' || c == 'o') {
19                count /= 2;
20            }
21            min = Math.min(min, count);
22        }
23        return min;
24    }
25}
  • Time Complexity: O(n)
  • Space Complexity: O(1) because we can have at most 26 unique keys as lowercase English characters.

Using Arrays

In this case, the constraint mentions that all characters are lowercase English characters. That means we can have at most 26 unique characters. So, we can store count of each character occurrences in the array of size 26. Once we have stored occurrences of characters of the text, we have to verify how many times we can create word pattern using these characters.

 1class Solution {
 2    public int maxNumberOfBalloons (String text) {
 3        int[] counts = new int[26];
 4        for (char c: text.toCharArray()) {
 5            counts[c - 'a']++;
 6        }
 7        int min = Integer.MAX_VALUE;
 8        // Check maximum how many times each character in wordPattern can be found in text
 9        for (char c: "balloon".toCharArray()) {
10            int count = counts[c - 'a'];
11            if (c == 'l' || c == 'o') {
12                count /= 2;
13            }
14            min = Math.min(min, count);
15        }
16        return min;
17    }
18}
  • Time Complexity: O(n)
  • Space Complexity: O(1) as maximum 26 is the size of the array we need.