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.
