aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwzzyyzzabc output:
Length of largest unique substring : 51 Sorry it gt posted thrice. > > On Jul 22, 7:50 pm, [email protected] wrote: > > https://ideone.com/kzo2L > > > > Regards > > Vaibhav Mittal > > Computer Science > > Netaji Subhas Institute Of Technology > > Delhi. > > > > On , Pankaj <[email protected]> wrote: > > > > > > > > > > > > > > > > > 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 az. > > > > > 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. > > -- > 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.
