Balloon Everywhere
Bob is very fond of balloons. Once he visited an amusement park with his mother. The mother told Bob that she would buy him a balloon only if he answer her problem right. She gave Bob a string S [contains only lowercase characters] and asked him to use the characters of the string to form as many instances of the word “balloon” as possible. Return the maximum number of instances that can be formed.
Help Bob to solve the problem.
Note: You can use each character in the string at most once.
Examples:
Input: S = “nlaebolko”
Output: 1
Explanation: Here, the number of occurrences of ‘b’ = 1, the occurrence of ‘a’ = 1, the occurrence of ‘l’ = 2, the occurrence of ‘o’ = 2, the occurrence of ‘n’ = 1. So, we can form 1 “balloon” using the letters.Input: S = “loonbalxballpoon”
Output: 2
Explanation: Here, the number of occurrence of ‘b’ = 2, occurrence of ‘a’ = 2, occurrence of ‘l’ = 4, occurrence of ‘o’ = 4, occurrence of ‘n’ = 2. So, we can form 2 “balloon” using the letters.
Approach: To solve the problem follow the below idea and steps:
So, to form “balloon” 1 time we need at least 1->b, 1->a, 2->1, 2->o, 1->n.
- So, for checking this we have to store the frequency of elements of string S.
- We do so by taking an array of size 26 as there are total 26 characters.
- After that, we run a loop to check how many times we can make a balloon and if at any point we won’t be able to make it then we will return our answer.
Below is the implementation for the above approach:
C++
// C++ code to implement the same #include <bits/stdc++.h> using namespace std; // Function which returns the number of // such instances. int maxInstance(string S) { // Array to store frequency int arr[26] = { 0 }; // Storing frequency for ( char x : S) arr[x - 'a' ]++; int ans = 0; // Run loop until we do not get // instance of "balloon" while ( true ) { if (arr[ 'b' - 'a' ] and arr[ 'a' - 'a' ] and (arr[ 'l' - 'a' ] > 1) and (arr[ 'o' - 'a' ] > 1) and arr[ 'n' - 'a' ]) { ans++; arr[ 'b' - 'a' ]--; arr[ 'a' - 'a' ]--; arr[ 'l' - 'a' ] -= 2; arr[ 'o' - 'a' ] -= 2; arr[ 'n' - 'a' ]--; } else return ans; } } // Driver's code int main() { // String to evaluate string S = "nlaebolko" ; // Calling function and printing value cout << maxInstance(S) << endl; return 0; } |
Java
// Java Code implementation import java.io.*; class GFG { // Function which returns the number of such instances. static int maxInstance(String S) { // Array to store frequency int [] arr = new int [ 26 ]; // Storing frequency for ( char x : S.toCharArray()) arr[x - 'a' ]++; int ans = 0 ; // Run loop until we do not get instance of // "balloon" while ( true ) { if (arr[ 'b' - 'a' ] > 0 && arr[ 'a' - 'a' ] > 0 && arr[ 'l' - 'a' ] > 1 && arr[ 'o' - 'a' ] > 1 && arr[ 'n' - 'a' ] > 0 ) { ans++; arr[ 'b' - 'a' ]--; arr[ 'a' - 'a' ]--; arr[ 'l' - 'a' ] -= 2 ; arr[ 'o' - 'a' ] -= 2 ; arr[ 'n' - 'a' ]--; } else { return ans; } } } public static void main(String[] args) { // String to evaluate String S = "nlaebolko" ; // Calling function and printing value System.out.println(maxInstance(S)); } } // This code is contributed by karthik. |
Python3
# Function which returns the number of # such instances. def max_instance(S): # Array to store frequency arr = [ 0 ] * 26 # Storing frequency for x in S: arr[ ord (x) - ord ( 'a' )] + = 1 ans = 0 # Run loop until we do not get # instance of "balloon" while True : if arr[ ord ( 'b' ) - ord ( 'a' )] and arr[ ord ( 'a' ) - ord ( 'a' )] and (arr[ ord ( 'l' ) - ord ( 'a' )] > 1 ) and (arr[ ord ( 'o' ) - ord ( 'a' )] > 1 ) and arr[ ord ( 'n' ) - ord ( 'a' )]: ans + = 1 arr[ ord ( 'b' ) - ord ( 'a' )] - = 1 arr[ ord ( 'a' ) - ord ( 'a' )] - = 1 arr[ ord ( 'l' ) - ord ( 'a' )] - = 2 arr[ ord ( 'o' ) - ord ( 'a' )] - = 2 arr[ ord ( 'n' ) - ord ( 'a' )] - = 1 else : return ans # Driver's code if __name__ = = '__main__' : # String to evaluate S = "nlaebolko" # Calling function and printing value print (max_instance(S)) |
Javascript
function maxInstance(S) { // Array to store frequency const arr = new Array(26).fill(0); // Storing frequency for (const x of S) { arr[x.charCodeAt(0) - 'a' .charCodeAt(0)]++; } let ans = 0; // Run loop until we do not get // instance of "balloon" while ( true ) { if (arr[ 'b' .charCodeAt(0) - 'a' .charCodeAt(0)] && arr[ 'a' .charCodeAt(0) - 'a' .charCodeAt(0)] && (arr[ 'l' .charCodeAt(0) - 'a' .charCodeAt(0)] > 1) && (arr[ 'o' .charCodeAt(0) - 'a' .charCodeAt(0)] > 1) && arr[ 'n' .charCodeAt(0) - 'a' .charCodeAt(0)]) { ans++; arr[ 'b' .charCodeAt(0) - 'a' .charCodeAt(0)]--; arr[ 'a' .charCodeAt(0) - 'a' .charCodeAt(0)]--; arr[ 'l' .charCodeAt(0) - 'a' .charCodeAt(0)] -= 2; arr[ 'o' .charCodeAt(0) - 'a' .charCodeAt(0)] -= 2; arr[ 'n' .charCodeAt(0) - 'a' .charCodeAt(0)]--; } else { return ans; } } } // Driver's code const S = "nlaebolko" ; // Calling function and printing value console.log(maxInstance(S)); //this code is contributed by Tushar Rokade |
C#
//C# equivalent using System; class GFG { // Function which returns the number of such instances. static int maxInstance(String S) { // Array to store frequency int [] arr = new int [26]; // Storing frequency foreach ( char x in S.ToCharArray()) arr[x - 'a' ]++; int ans = 0; // Run loop until we do not get instance of // "balloon" while ( true ) { if (arr[ 'b' - 'a' ] > 0 && arr[ 'a' - 'a' ] > 0 && arr[ 'l' - 'a' ] > 1 && arr[ 'o' - 'a' ] > 1 && arr[ 'n' - 'a' ] > 0) { ans++; arr[ 'b' - 'a' ]--; arr[ 'a' - 'a' ]--; arr[ 'l' - 'a' ] -= 2; arr[ 'o' - 'a' ] -= 2; arr[ 'n' - 'a' ]--; } else { return ans; } } } public static void Main(String[] args) { // String to evaluate String S = "nlaebolko" ; // Calling function and printing value Console.Write(maxInstance(S)); } } |
1
Time Complexity: O(N), where N is the length of S
Auxiliary Space: O(26).