http://www.codechef.com/problems/ABCSTR (link of question)

- 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

2 Likes

@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