Here is my algo: 1)Replace all '0' with '1' and '1' with '-1'(.i.e, 1 0 1 ---> -1 1 -1)
2)Now take an array to calculate the sum of all elements from 1 to that index, which can be calculated as sum[i]=sum[i-1]+ar[i],take 0th element as 0. 3)Now the problem becomes finding two indices (say i,j) for which, sum[i]=sum[j] and j-i is maximum (j>i) (This is easy to see as,Let for substring [i,j] the number of 1s is equal to number of 0's ,then sum[i,j]=0 as per our algo, OR we can state that sum[i-1]=sum[j],now for longest substring the difference should be maximum) example:- 1 0 1 --> -1 1 -1 ---> sum array :: 0 -1 0 -1 take i=1and j=2,sum[i-1]=sum[j]=-1,and substring::string[1,2]= 1 0 (Answer) 4)Now,the above step can be done quickly using hashing(using array indexes) in O(n).(If n<10^6) On Sat, Aug 13, 2011 at 9:53 PM, Yasir <[email protected]> wrote: > Me too didn't get Raghavan's algo... Pls explain.. > It seems that above algo will find only longest sequence starting from > index 0. > > Just a thought: > Along with raghavan's algo, what if I keep and > array_of_integers[string_length] > and keep on storing the count in this array. > > Once string is traversed we have to find the max distance among two equal > numbers in an array. (need to think on this problem as well) > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/gWwbzXZ_B1sJ. > > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- *Regards,* *Piyush Kapoor,* *2nd year,CSE IT-BHU* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
