Vaibhav What 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: > Vaibhav > What 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.
