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:

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.