Thanks, my approach prepare a multimap of charcters and their positions by walking over the string.
ashishis if is give string the multimap will have a->0 s->1,4,7 h->2,5 i->3,6 now for every character while walkingover the given string again, check from its multimap, if it is repeated, if not continue to next char. but if it is for all possible differences w.r.t this position, find the repeated string eg for s the values are 4-1=3 and 7-1=6 so if the string repeats than the next 3-1 or 6-1 chars should also have the diff exactly the same the next tow chars are h and i for h current pos is 2 and the diff is 5-2=3 which is good for i current pos is 3 and the diff is 6-3=3, hence shi is indeed a repeating string immediately and hence it is not a valid string. Had it not matched, we would have started for string of length 6 starting at a[7]. hope this helps. But this is not O(n) algo. O(n2) actually in worst case. Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Wed, Jun 6, 2012 at 12:52 PM, atul anand <[email protected]> wrote: > nope geke is valid string.. > > here is the link from where question was taken > > > http://geeksforgeeks.org/forum/topic/amazon-interview-question-password-checker > > > On Wed, Jun 6, 2012 at 11:44 AM, Ashish Goel <[email protected]> wrote: > >> Hassan geke should not be a valid string. The question states " which >> have the same substring following it " so here e follows e. There is no >> precondition that it has to follow immediate. >> >> Utsav: can you clarify? >> >> >> Best Regards >> Ashish Goel >> "Think positive and find fuel in failure" >> +919985813081 >> +919966006652 >> >> >> On Tue, Jun 5, 2012 at 11:32 PM, Hassan Monfared <[email protected]>wrote: >> >>> yes It's valid, cuz it doesn't have any repeated substring next together >>> >>> >>> On Tue, Jun 5, 2012 at 7:08 PM, Lomash Goyal <[email protected]>wrote: >>> >>>> is geke is a invalid strng? >>>> >>>> >>>> On Tue, Jun 5, 2012 at 12:17 PM, Hassan Monfared >>>> <[email protected]>wrote: >>>> >>>>> Ashish: >>>>> >>>>> the algorithm passes over string and check if there is any substring >>>>> with len=1 is repeated or not. if not, tries for substring with len 2,... >>>>> and so on. >>>>> max length of substring which can be repeated can be at most N/2. >>>>> >>>>> >>>>> Regards, >>>>> >>>>> >>>>> On Tue, Jun 5, 2012 at 10:48 AM, Ashish Goel <[email protected]>wrote: >>>>> >>>>>> The problem suggests that a character can't be more than once present >>>>>> and thereby it can be done by just having s bitmap and if a char repeats, >>>>>> any longer repeating substring will have those char repeated atleast >>>>>> twice, >>>>>> hence O(n) solution. >>>>>> >>>>>> >>>>>> Also, Hasaan: how is your algo O(n2) for for->while->for chain? >>>>>> >>>>>> Best Regards >>>>>> Ashish Goel >>>>>> "Think positive and find fuel in failure" >>>>>> +919985813081 >>>>>> +919966006652 >>>>>> >>>>>> >>>>>> On Tue, Jun 5, 2012 at 11:42 AM, Ashish Goel <[email protected]>wrote: >>>>>> >>>>>>> Hassan, can you explain your algo? >>>>>>> >>>>>>> Best Regards >>>>>>> Ashish Goel >>>>>>> "Think positive and find fuel in failure" >>>>>>> +919985813081 >>>>>>> +919966006652 >>>>>>> >>>>>>> >>>>>>> On Mon, Jun 4, 2012 at 11:20 AM, Hassan Monfared < >>>>>>> [email protected]> wrote: >>>>>>> >>>>>>>> for >>>>>>> >>>>>>> >>>>>>> >>>>>> -- >>>>>> 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. >>>>>> >>>>> >>>>> -- >>>>> 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. >>>>> >>>> >>>> >>>> >>>> -- >>>> Regards >>>> >>>> Lomash Goyal >>>> >>>> * >>>> * >>>> >>>> >>>> -- >>>> 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. >>>> >>> >>> -- >>> 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. >>> >> >> -- >> 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. >> > > -- > 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. > -- 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.
