CK87GSUB editorial (unofficial)

let a string s=“aaaa”

there are 6 good string as:

3 subarray of length 2:[aa] [aa] [aa]

2 subaaray of length 3:[aaa] [aaa]

1 subarray of length 4:[aaaa]

So for string of only one character there will be l*(l+1)/2 where l=length of subarray of same character

Now for string s=“aaabbb”
calculate subarray of character ‘a’ and ‘b’.add simply.

last for string s=“abbba”

length of subarray of character b and check if character before initial ‘b’ and after final ‘b’ is same or not and add+1 to answer

here is my solution:https://www.codechef.com/viewsolution/15926610

3 Likes

Can anyone help me out by telling me of tricky test cases where my code fails ? Link: https://www.codechef.com/viewsolution/15938027
Thanks.

@doramon
I thought of the same idea…bt got WA :frowning:
Can u explain what is the need of k = max(0, j-i-1) can’t we directly use k = j-i-1 instead?

@doramon

for the substring having only one character, of length l, good strings will be equal to (l * (l-1))/2 and not l*(l+1)/2.

Because l**(l+1)/2 also gives us 4 subarray of length 1:[a] [a] [a] [a] for string s=“aaaa”

(4*5)/ 2 = 10…

4 subarray of length 1:[a] [a] [a] [a]

3 subarray of length 2:[aa] [aa] [aa]

2 subaaray of length 3:[aaa] [aaa]

1 subarray of length 4:[aaaa]

but we don’t want 4 sub-arrays of length 1, we need the minimum length of 2.

So, we need to subtract l from l**(l+1)/2 which gives us (l*(l-1)/2).

But you are still getting the correct answer because you took the subarray length as (l-1) and not as l.

So, by using your formula , (((m)(m+1))/2) = (((l-1)(l-1+1))/2) = (l * (l-1))/2.

1 Like

@ashish53v is right!!

Any idea what test case I might have missed?
https://www.codechef.com/viewsolution/15941870

that will be same.u can use it.

suppose s=“bba”

for char ‘a’ i=2 j=3

k=3-2-1=0

k will be always non-negative

hope u get it.

i don’t get ur question!!