plz help...how to solvethis question..???(abc string)

ABCSTR Problem - CodeChef (link of question)

You can go through it’s editorial here : http://discuss.codechef.com/problems/ABCSTR

1 Like
  • 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

@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 :slight_smile: