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

×

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

 0 http://www.codechef.com/problems/ABCSTR (link of question) asked 01 Jul '14, 02:45 1●3 accept rate: 0%

 2 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 answered 01 Jul '14, 08:49 2★pudge 758●4●13 accept rate: 37% @pudge, how many substrings should i need to consider from j to i ... ?? (01 Jul '14, 13:14) @va1ts7_10: you need to check every 'j'(i.e 0<=j
 1 You can go through it's editorial here : http://discuss.codechef.com/problems/ABCSTR answered 01 Jul '14, 08:38 2.2k●6●17●48 accept rate: 10%
 toggle preview community wiki:
Preview

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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