*abcdea*ifjlbmnodpq 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.
