http://www.codechef.com/problems/ABCSTR (link of question)
You can go through it’s editorial here : http://discuss.codechef.com/problems/ABCSTR
- let A be any array to store all A’s appearing in String S now A[i] represents the number of A’s appeared till index ‘i’ of the string similarly for B to store number of B’s and C to store number of C’s
- 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.
- 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]
- 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]
- Go from left to right and for each index i find the number of valid good sub-strings which ends at i
@pudge, how many substrings should i need to consider from j to i … ??
@va1ts7_10: you need to check every ‘j’(i.e 0<=j<i), if you do that in O(n^2)(i.e nested loops) it will lead you to TLE. so think in a smart way. I just gave you hint how to solve because i don’t want to tell you entire logic. I hope you understand