doramon
1
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:CodeChef: Practical coding for everyone
3 Likes
Can anyone help me out by telling me of tricky test cases where my code fails ? Link: CodeChef: Practical coding for everyone
Thanks.
@doramon
I thought of the same idea…bt got WA 
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
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!!