Vaibhav, Ok write your code and paste on ideone. It should be easy and quick to code :)
On Fri, Jul 22, 2011 at 7:59 PM, <[email protected]> wrote: > U hv got my algo completely wrong. Gimme a smaller test case so that i may > wrk it out fr u. This one is freakingly large :P. > > > Regards > Vaibhav Mittal > Computer Science > Netaji Subhas Institute Of Technology > Delhi. > > On , Pankaj <[email protected]> wrote: > > abcdeaifjlbmnodpq > > For this once you encounter a at 6th position, You can update your > max.Now You will have to do following operation. > > First clear all the hash. > > 2. You now can not start from 6th position. You will have to do back and > start from 2 position that is b. > > > > > > > > > > Right? > > What is the maximum unique string in above test case? > > Try printing each sub string formed whenever you hit a duplicate. > > It's still O(N) though if we have constant number of characters :) > > > > > > > > > > On Fri, Jul 22, 2011 at 7:50 PM, [email protected]> wrote: > > > > > > Have a look again. I traverse the string just once performing updation on > variables low, high, max. I assume array operations to be O(1) (which they > are). OVerall complexity is O(n).Once I hit a duplicate i change my low, > high and A accordingly and move forward. > > > > > > > > Regards > > Vaibhav Mittal > > Computer Science > > Netaji Subhas Institute Of Technology > > Delhi. > > > > > > On , Pankaj [email protected]> wrote: > > > > > > > VaibhavWhat do you think the complexity of your algo is. And once you > hit an duplicate, from where will you start again? > > > Try for this example > > > abcdeaifjlbmnodpq. > > > It will be still O(26*n) as at max, we would have to start from each > letter and go forward maximum 26times( if we reach 26 then we have it > largest possible unique string). Otherwise keep checking. > > > > > > > > > > > > > So overall maximum complexity can be (MAX*n) where max will be unique > letters. > > > Abhishek, I think the final complexity can never be O(n^2) if you only > consider unique letters a-z. > > > The suggested soln is purely bruteforce. If anyone can think of a > better solution then please reply. > > > > > > > > > > > > > > > > > > > Cheers > > > Pankaj > > > > > > On Fri, Jul 22, 2011 at 7:37 PM, Pankaj [email protected]> > wrote: > > > > > > > > > > > > > > > > > > VaibhavWhat do you thing the complexity of your algo is. And once you > hit an duplicate, from where will you start again? > > > > > > > > > > > > > > > > > > > > > > > > On Fri, Jul 22, 2011 at 7:21 PM, [email protected]> wrote: > > > > > > > > > String is "abcded" > > > l =0, h = 0 > > > > > > > i = 1, l = 0, h = 1, max = 1, A[a]=1 > > > i = 2, l = 0, h = 2, max = 2, A[b] = 2 > > > > > > > > > > > > > > > i = 3, l = 0, h = 3, max = 3, A[c] = 3 > > > i = 4, l = 0, h = 4, max = 4, A[d] = 4 > > > > > > > i = 5, l = 0, h = 5, max = 5, A[e] = 5 > > > i = 6, 'd' is encountered again, update l = A[d] = 4, new A[d] = 5, h = > 6, max = max(5, 6-4)= max(5, 2) = 5 > > > > > > > > > > > > > > > > > > hence ur ans = 5 > > > > > > > > > > Regards > > > Vaibhav Mittal > > > Computer Science > > > Netaji Subhas Institute Of Technology > > > Delhi. > > > > > > > > > On , Interstellar Overdrive [email protected]> wrote: > > > > > > > > > > > > > > > > > > > > @svm11: Take the case with original string "abcded" output should be > 5 but your algo will give the answer as 0. > > > > > > > > > > > > > > > > > > > > > > > > -- > > > > > > > > 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/-/hG6ZNcG5fMMJ. > > > > > > > > > > > > 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. > > > > > > > > > > -- > 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.
