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.
