Welcome back.
Let's now go ahead and code the solution which we discussed in the previous video.
For this we are going to write a function.
Let's call it max length.
And this function is going to take in the string which is given to us.
All right.
Now inside this function let's have a variable which is called max.
And let's initialize this to zero.
So this is going to be the maximum length of the substring where the characters are unique.
So we're going to find that.
And finally we will return this value.
So this is the function that we are trying to write.
Now we will also need a variable called start.
And initially this will point to the zeroth index right.
And when we encounter a character which is repeating we will see whether we have to change the start
or not.
And we will need a hash table.
Let's just call it scene.
And initially it's empty.
All right.
Now we are going to traverse the string which is given to us.
So let's use a for loop for let I is equal to zero I less than string dot length I plus plus.
Right now at each index I we are going to take the character so we can say const char is equal to string
at I.
So we get that particular character.
Now let's check whether it is there in the hash table.
So if it's already there that means it occurred previously in the string which we are traversing.
So let's check that.
So if char in seen so if it's there in our hash table then we have to see whether we have to change
the start or not.
So we say start is equal to math dot max between start.
That is the existing value of start and the value in the hash table for that particular character which
is seen at char plus one.
So we have to take the maximum among these two and set that to start.
So what is happening over here.
Let's take an example.
Let's say the string which is given to us is a b c b d e f.
Now when we encounter the second b, we will see that we have already entered b two our hash table.
Again, we have not written the code for that, but we will be writing it below over here.
All right.
So we will make an entry.
Into the hash table.
If it's not there.
So we are going to do that.
So let's say we have already made this entry.
And when we come to the second B we will find that it is already there.
Right.
So we cannot take this this substring to be consisting of unique characters.
So we have to see whether we have to move the start point.
And over here we can see that at this point the start is over here.
Right.
And this b the first B is occurring after the start happen.
So we have to move the start to this place.
So that is what we are checking over here.
We are checking the maximum between zero.
In this case start is at zero and then seen at char will be one right.
That would be this index plus one which is two.
So among zero and two two is the greater value.
So for in this case we will move start to two.
And then we will see how many characters we can take together to get the longest substring.
And in this case it's going to be of length five right.
C b d e and f.
So that is what we are doing over here.
Now once we have changed the start, if necessary we will go ahead and update our max value.
Right?
So Max is tracking the maximum length of the substring which is consisting of unique characters.
So Max is going to be again the maximum math dot max between the existing value which is there in max,
and the difference between I and start plus one.
Why is that so?
Let's take a look at our example over here a b c b d e f.
Let's say we are at the second character over here.
Now start is at zero.
Now B the index where we are at right now is one.
Right.
So we can say that the the length of this substring AB is the index of b which is one minus start.
So one -0 is equal to one plus one.
So that's why we have I minus start plus one.
Again we have this plus one over here because the indices start from zero over here.
Right.
So we are we are taking I is equal to zero initially and the indices are starting from zero.
So that is why we are doing plus one over here.
So this ensures that the length of the maximum substring with unique characters is stored to the max
variable.
And then we are just going to make an entry into our hash table if that particular character is not
there as a key in our hash table.
So let's do that scene at char.
Is equal to I.
Now there are two cases.
If it's not there.
Let's say for example, we are encountering B for the first time.
It will not go to this place.
And at this point it will make a fresh entry to our visited, uh, to our scene hash table.
Now, if it's already there.
And in that case, when we come over here, we are going to update the value.
Right?
We are going to update the value to the index where the particular character is occurring, the latest
time.
So for example let's again take this example and let's look at B.
So over here we can see that B is first encountering is is coming up at index one.
And then B is coming again at index three.
Right.
So this is index three.
So initially in our scene hash table the value for key b will be one.
But when we see the second b we will update the value to three.
So that is what is happening over here.
All right.
So we are done.
And that's it.
So we are done with our function.
So this should work.
Now let's go ahead and test our function for this.
Let's just try some.
Strings, so I call the max length function.
And let's say we pass a simple string a, b, c, d, and then let's have b.
Now let's run it.
Now we can see that we get the maximum length as four, which is correct.
Right?
So a b, c, d this is the maximum uh length of the substring.
So this is the greatest substring with unique characters.
And we can see that its length is four.
Now what if we have something else over here.
Let's just add some more, uh, uh, string characters over here.
And let's run it.
So we get ten over here.
So definitely it's not this right.
It should not start over here.
So let's see this part over here.
What's the length over here 123.
And include we can include this B.
We can include this C also.
Right.
So we just cannot include this B because there is a b over here.
So let's look at this string 123456789 and ten.
And we cannot take this D because we have a D over here.
Right.
So we cannot take this D.
So we take this one over here and we can start over here.
So this is the greatest substring right.
The longest substring.
So it has 3456789 and ten as the length.
So yes our function is working.
Let's just try one more thing.
Let's just try one more.
Let's say p q b r s t.
Be you.
VW.
V x y.
So let's see.
And over here yes you can see we are getting the length seven which is correct.
Right.
So that's starting over here we have 3456 and seven.
So this is the greatest substring with unique characters.
And the length of it is seven.
So our function is working.
Now let's take a sample input and again run through the code and see what's happening.
And let's also relook at the space and time complexity of our solution.