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 <jatka.oppimi...@gmail.com> 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, vaibhavmitta...@gmail.com> 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 jatka.oppimi...@gmail.com> 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 jatka.oppimi...@gmail.com>
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, vaibhavmitta...@gmail.com> 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 abhi123khat...@gmail.com> 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 algogeeks@googlegroups.com.
>
>
>
>
> >
> > To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
> >
> >
> > 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 algogeeks@googlegroups.com.
>
> To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
>
>
> 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 algogeeks@googlegroups.com.
>
> To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
>
>
> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
