GOODPREF Unofficial Editorial(April Long)

PROBLEM LINK:

Div1

Div2

Editorialist:- Vikram Jeet Shyoran

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

Given a string s and an integer n, full string S is concatenating string s n times.

Find the number of non_empty prefixes of t in which the number of occurrences of 'a' is strictly greater than the number of occurrences of 'b'.

EXPLANATION:

string S= whole string after concatenating n times string s

string s = Given string

int ans=  number of non_empty prefixes of t in which the number of occurrences of 'a' is strictly  greater than the number of occurrences of 'b'

int temp= ans in s

let x = count of character 'a' in s

      y= count of character 'b' in s

Here  we have 3 cases in keeping in mind x and y :-

1) x=y

2)x>y

3)x<y

let's do the analysis for each case:-

Case # 1: When x=y

if n=1 , ans=temp

if n=2 , ans= 2*temp

if n=3, ans= 3*temp

....

...

...

if n=n , ans= n*temp

Case# 2: When x>y

countA= count of char 'a'

countB= count of char 'b'

for  n=1 , countA=x, countB=y

for n=2  , countA=2*x,countB=2*y

for n=3  ,countA=3*x, countB=3*y

...

...

...

for n=t,  countA=t*x, countB=t*y

In this case, there will be a time when countA-countB>=length(s) after t whole string s will contribute in ans. So we will count till n=t manually using for loop and after that, we add (n-t)*temp

Case# 3: When x<y

This case is similar to the 2nd case. Ther will be a t when countB-countA>=lenght(s), after that t no string will contribute in ans. So our ans will be until n=t.

if n< t then we calculate ans using for loop.

IMPLEMENTATION:

	#include<bits/stdc++.h>
	using namespace std;
	int main(){
	int t;
	cin>>t;
	while(t--){
	string s; // Given string
	cin>>s;
	long long n; // Given interger
	cin>>n;
	int a=0,b=0; // countA and countB in string s
	for(int i=0;i<s.size();i++){
	if(s[i]=='a')
	a++;
	else b++;
	}
	long long cnt=0; //countA and coutnB in string S(concatinated t times)
	long long cntA=0,cntB=0;
	for(int i=0;i<s.size();i++){
	if(s[i]=='a')
	cntA++;
	else cntB++;
	if(cntA>cntB)
	cnt++;
	}
	//Case# 1: where x=y
	if(a==b){
	cout<<cnt*n<<endl;
	continue;
	}
	//Case# 2 and Case# 3
	int flag=0;
	cntA=0;
	cntB=0;
	cnt=0;
	int i;
	for(i=0;i<n;i++){
	if(cntB+b<cntA){
	flag=1;
	break;
	}
	if(cntA+a<cntB){
	flag=2;
	break;
	}
	for(int j=0;j<s.size();j++){
	if(s[j]=='a')
	cntA++;
	else cntB++;
	if(cntA>cntB){
	cnt++;
	}
	}
	}
	if(flag==0||flag==2)
	cout<<cnt<<endl;
	else if(flag==1)
	cout<<cnt+(n-i)*s.size()<<endl;
	}
	return 0;
	}

view raw GOODPREF code hosted with ❤ by GitHub

If I am wrong somewhere please point it out, I will be grateful to you.
If you didn't understand something just put a comment I will try to clear your doubt.