here is the link of my problem…http://www.codechef.com/problems/ABCSTR
when i read the editorials , then i came to know this…
!.let A be any array to store all A’s appearing in String S now A[i] represents the number of A’s appeared 2.till index ‘i’ of the string similarly for B to store number of B’s and C to store number of C’s
3.Now if you wan’t to find number of A’s that appeared between the index ‘j’ and ‘i’ (i>j) is nothing but A[i] - A[j-1] (you can verify it easily) similarly for B and C.
4.Now for sub-string to be good the necessary condition is A[i]-A[j-1]=B[i]-B[j-1]=C[i]-C[j-1]
5.or the above one can be re written as A[i]-B[i]=A[j-1]-B[j-1] && A[i]-C[i]=A[j-1]-C[j-1]
6.Go from left to right and for each index i find the number of valid good sub-strings which ends at i
my algo takes o(n^2)(by using nested loops) time to execute this solution… can anyone plzzz help me how to reduce the runtime of this problem…??
i am using C language for my code.