You are not logged in. Please login at www.codechef.com to post your questions!

×

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

asked 01 Jul '14, 02:45

va1ts7_10's gravatar image

1★va1ts7_10
13
accept rate: 0%


  • 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
link

answered 01 Jul '14, 08:49

pudge's gravatar image

2★pudge
758413
accept rate: 37%

edited 01 Jul '14, 08:52

@pudge, how many substrings should i need to consider from j to i ... ??

(01 Jul '14, 13:14) va1ts7_101★

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

(01 Jul '14, 18:06) pudge2★

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

link

answered 01 Jul '14, 08:38

achaitanyasai's gravatar image

5★achaitanyasai
2.2k61748
accept rate: 10%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×643
×4

question asked: 01 Jul '14, 02:45

question was seen: 1,432 times

last updated: 01 Jul '14, 18:06