FAANG - Editorial

PROBLEM LINK:

Contest

Author: Sumukh Bhardwaj
Tester: Rahul Sharma
Editorialist: Sumukh Bhardwaj

DIFFICULTY:

EASY

PREREQUISITES:

Basic Programming

PROBLEM:

Given a string S having lowercase English letters, find the number of instances of google can be formed using the characters from S.

QUICK EXPLANATION:

Count the instances of g, o, l, and e, let these be w, x, y and z find the minimum of {w/2,x/2, y, z}.

EXPLANATION:

Find the count of all the four characters (g, o, l, and e) in the string S. Each instance of google needs 2 instances of g, 2 instances of o, 1 instances of l and 1 instances of e. Hence number of possible instances of google that can be formed from w instances of g is actually be w/2 similarly for o, x instance can form x/2 instances of google. Other characters needs to be present in single quantity to make one google. Therefore the number of google instances will be equal to the bottleneck character instances which will be minimum of {w/2,x/2, y, z}.

Here, w is frequency of g in S, x is frequency of o in S, y is frequency of l in S, z is frequency of e in S.

COMPLEXITIES

Here N is the size of S.

TIme Complexity:
O(N).
We are just traversing the array from left to right.

Space Complexity:
O(1)
We need 4 variables only, hence space complexity is constant.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

int solve(string text) {

int i,g=0, o=0,l=0,e=0,N = text.size();

for(i=0;i<N;i++)
{
	if(text[i] == 'g')
		g++;
	else if(text[i] == 'e')
		e++;
	else if(text[i] == 'l')
		l++;
	else if(text[i] == 'o')
		o++;
}

g /= 2;
o /= 2;

return min(g, min(o, min(l, e)));
}


int main() {
ios_base::sync_with_stdio(false);
int t;

cin>>t;

while(t--)
{
	string s;
	cin>>s;

	cout<<solve(s)<<endl;
}

return 0;
}
1 Like