Thanx for pointitn out the case :) Hope dis wil wrk. https://ideone.com/0LNkW
On , Pankaj <jatka.oppimi...@gmail.com> wrote:
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwzzyyzzabc output:
Length of largest unique substring : 51 Sorry it gt posted thrice.
On Jul 22, 7:50 pm, vaibhavmitta...@gmail.com wrote:
> https://ideone.com/kzo2L
>
> Regards
> Vaibhav Mittal
> Computer Science
> Netaji Subhas Institute Of Technology
> Delhi.
>
> On , Pankaj jatka.oppimi...@gmail.com> 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, vaibhavmitta...@gmail.com> 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 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.
> > --
> > 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.