@Abhi
See every character in the string is read exactly once and hashed. So
the complexity is O(n) only.
Mistake you're doing is adding n/2 n times, but if you see in your
example you have to add it twice only.
--
AP
--
You received this message because you are subscribed to the Google Groups
No, every character won't be read exactly once.
--
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/-/lU8COVBGWSwJ.
To post to this group, send email to
Oh yes you're right. Understood the algo incorrectly.
--
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
@khattri and khurana:
traverse the string once.
suppose the string is abcdeabcdeabcde
take a hashtable (initially set the items to -1) .now hash as per
khurana's idea till no duplicate occurs.Instead of marking 1. mark the
array index in the hashtable.
so in the hash table, we have
a=0 b=1 c=2 d=3
My algo for this prob:
Maintain an array A for characters from a-z which stores the index of
character encountered in the string. (initially all = -1)
iterate over all the characters in the string maintaining low and high
variables (initially both = 0) and max (initially = 0, stores length
of
@rawat: your algo doesn't compute the length of the largest unique
sub-string as far as I can infer or it needs further steps to be done.
Abhishek Khattri
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the
@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
sorry, for the previous post,
consider this...
iterate the string using variable i
'low' is another variable that stores the index of previous occurrence
of the character+1
initially, i=0 , low=0
max=i-low
abcdedepoiuytu
hashtable :
a= -1 , b= -1, . . . z = -1
a=0
b=1
c=2
d=3
e=4
now, d comes
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,
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, 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
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
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
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
*abcdea*ifjlbmnodpq
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
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
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,
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,
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,
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
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
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,
21 matches
Mail list logo
