Welcome back.
So this is the code that we have just now written.
Now let's take a sample input and walk through the code and see what's happening at each line over here.
Now let's say the string which is passed to the function is a b c b d e f.
All right.
Now let's say this is the string which is passed to it.
Now initially once we are inside the function max is set to zero and start is pointing to zero.
Right?
Start is equal to zero.
And then we have our hash table seen which is empty.
So seen.
Let me just write this over here C is empty at this point.
Now we are going to loop through the string which is given to us.
Initially I is equal to zero.
We take the character at string zero which is a right.
So this is zero, one, two, three, four, five and six.
So these are the indices.
So we take a.
Now we are checking whether A is there in seen it's not.
So we are going to make a mapping right.
So again that's happening over here.
We are checking whether it's there.
It's not there.
So we are going to update Max.
Now Max at this point is zero I is equal to zero at this point right.
And start is zero.
So zero -0 plus one.
So the max is zero.
And this part over here becomes one.
Now the maximum among zero and one is one.
So Max is updated to one.
At this point let me just track it over here itself.
Or or probably I can just do it at this side.
So let me just wrap this.
And over here I'll track Max.
So we have seen that Max has become one.
Now at this part we are going to make an entry into our scene hash table and scene at car.
Right char the the key is going to be the character which is a.
So the key is a and the value is going to be the index, which is zero.
At this point the index is zero.
Again we increment I, so I becomes one.
Now we take the character at index one which is b.
Now we are going to check whether B is in C.
No it's not there.
So again we're going to update max right.
So max at this point is one and I is equal to one.
So one -0 is one one plus one is two.
So among one and two two is the greater value.
So we update max to two.
And we are going to make an entry right.
So the key is going to be B and the value is going to be one.
Again I is incremented.
And we come to see over here again we are going to take it.
That's that's at this line.
We take C right.
We are checking whether C is there in our scene hash table.
It's not there.
Again we update max because this part is going to be three and max at currently is just two.
So this becomes three.
All right.
Again we increment I.
So I is going to point to index three.
So again we see over here that the value is b.
And at this point we see that b is already there in our scene hash table.
And again previously we have entered C.
So I forgot that.
So C is having the value two.
The key is c.
Now when we again came to B we see that it's there.
So we see it's there in our hash table.
So we are going to check whether we need to update the start.
Now in this case we have start pointing to zero.
So start at this point is pointing to zero and seen at char is is one and one plus one is two.
So among zero and two the greater value is two.
Therefore we will update the start value right.
So start is now going to point to this one over here which is two.
Because among zero and two two is the greater value.
Again from a logical perspective we are just checking whether start between start and the first in the
previous instance where that particular character occurred, which is greater.
Right.
Whether the the index where that character occurred plus one or start is greater.
So in this case this is greater.
So we change start to here.
And then we are going to check the length.
So in at this point max is three.
But the length between start and b is just two right.
So we are not going to update it again.
We are going to move I so I comes over here we see that D is not there here.
So we are going to check over here.
Max is three.
And the length over here is also three.
Right.
So that happens over here.
So we don't need to update this.
And we are going to make an entry D.
And the entry is going to be four.
Again we move I I comes over here.
Now at this point again we check whether E is there in scene.
It's not there.
Now we are going to see whether we have to update Max.
So over here the length of this substring is four right.
And this is three.
So we have to update this to four.
And we are going to make an entry for E as well.
So e and the value is five.
And again we update I I because I comes to six.
Now we are seeing that it's not there in our scene hash table.
So over here we are going to change the max value to five.
And we are making an entry f and six.
So in this way we are going to find that the length of the maximum substring of this string with unique
characters for this string, which is given to us, is equal to five.
Now that's what is happening.
So this is how our algorithm functions.
Now over here you can notice that we are taking the maximum between start and max.
Let's say for example over here after f for example let's say we have a okay.
So at this point the start is only here.
Start is over here right at index two.
So this is where start is.
Now if we encounter a after uh over here, then there is no point in shifting the start.
Right.
Because logically you can see that we have not started looking from here.
So that is what is happening over here.
So when we check whether we need to change start or not, we are just checking whether which is greater
is start greater, or is the index where that particular character occurred previously plus one.
Right.
So that that's what is computed over here is start greater or is this greater in this case seen at char
will be zero and zero plus one is one.
Right.
If A was there over here.
So among one and two two is greater.
So we don't need to move start.
And in that case we would have just incremented this.
And we could have taken this substring over here which has a length of six.
So this is how our how our algorithm functions.
Now let's.
Take a quick look at the space and time complexity.
Now, when it comes to the time complexity, it is pretty straightforward, right?
We are just traversing the given string once, so the time complexity is O of n if n is the length of
the given string.
So that is pretty straightforward.
So for each value of I we are just doing some constant time operations.
Now what about the space complexity.
Now let's take a look at what all things consume scaling type of space.
Right.
So you can see that it's only this hash table over here.
Now the space complexity therefore will depend on the size or the amount of space our hash table will
take.
Now in this case, we can say that the space complexity is of the order of the minimum between n and
M, where m is the number of unique characters in our string.
So the number of unique characters in our string will depend how big our hash table is going to be.
Right?
Because we are, we are going to make only entries for unique characters.
So.
And the worst case is if all the N characters are unique, in that case, the space complexity will
be O of n, otherwise the space complexity is going to be of the order of the minimum between n and
m, where n is the length of the string which is given to us, and m is the number of unique characters
in the string unique characters.
So this is unique characters in the string.