Sponsored
Sponsored
This approach involves counting the frequency of each character in the string 'text' and then determining how many full instances of the word 'balloon' can be formed based on these frequencies. We will count the occurrences of the characters 'b', 'a', 'l', 'o', and 'n'. Since 'l' and 'o' appear twice in the word 'balloon', their counts should be halved. Finally, we find the minimum number of complete 'balloon' words that can be formed using these character counts.
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), since we are using a constant amount of extra space.
1import java.util.HashMap;
2import java.util.Map;
3
4public class Solution {
5 public int maxNumberOfBalloons(String text) {
6 Map<Character, Integer> count = new HashMap<>();
7 for (char c : text.toCharArray())
8 count.put(c, count.getOrDefault(c, 0) + 1);
9 count.put('l', count.getOrDefault('l', 0) / 2);
10 count.put('o', count.getOrDefault('o', 0) / 2);
11 return Math.min(Math.min(Math.min(Math.min(count.getOrDefault('b', 0), count.getOrDefault('a', 0)), count.getOrDefault('l', 0)), count.getOrDefault('o', 0)), count.getOrDefault('n', 0));
12 }
13
14 public static void main(String[] args) {
15 Solution solution = new Solution();
16 System.out.println(solution.maxNumberOfBalloons("loonbalxballpoon"));
17 }
18}This Java solution uses a HashMap to count characters in the input string and adjusts counts for 'l' and 'o'. It then finds the minimum count of required characters to determine the number of 'balloon' words that can be formed.
Instead of counting characters explicitly, this approach calculates the maximum number of 'balloon' instances by directly comparing the ratios of character counts required. Specifically, for 'b', 'a', and 'n', the ratio is 1:1, but for 'l' and 'o', the ratio is 1:2 in 'balloon'. This approach simplifies checking character sufficiency by calculating the feasible number of 'balloon' words based on the complete sets of these character combinations.
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), as it uses a fixed number of variables for counting.
public class Solution {
public int MaxNumberOfBalloons(string text) {
int b = 0, a = 0, l = 0, o = 0, n = 0;
foreach (char c in text) {
if (c == 'b') b++;
else if (c == 'a') a++;
else if (c == 'l') l++;
else if (c == 'o') o++;
else if (c == 'n') n++;
}
l /= 2;
o /= 2;
return Math.Min(b, Math.Min(a, Math.Min(l, Math.Min(o, n))));
}
public static void Main() {
Solution solution = new Solution();
Console.WriteLine(solution.MaxNumberOfBalloons("loonbalxballpoon"));
}
}The C# solution uses individual integer variables for directly counting relevant characters and dividing 'l' and 'o' by 2. It calculates the minimum count to produce the most complete 'balloon' words based on characters available.