Welcome back.
Let's now think about how we can solve this question.
First, let's think about the brute force method.
We could identify all the possible substrings.
For example substrings of length one character, substrings of length two character substrings of length
three characters, etc., and up to substrings of the length of the given string.
This would be the last string, right?
So that is one way we could just find all the substrings which are possible, and from all the substrings
we can identify the substrings which are made up of unique characters.
And then among those substrings we can find the substring of maximum length, identify its length and
return it.
So this would be the brute force method of solving this question.
Now what would be the time complexity of this method?
We know that if we have a string of length n, then the number of substrings that string would have
will be of the order of n square.
Why is that?
So let's take an example.
Let's say we have a string a, b, c, d, e.
Now I can have five substrings of length one, right?
I can have four substrings of length two.
That is a, b, b, c, c, d, and d I can have three substrings of length three, a, b, c, b,
c, d and c, d, e, etc. and finally I will have one substring of length five over here.
Right.
So five plus four plus three plus two plus one.
Now if I have a string of length n in that case the number of substrings would be one plus two plus
three etc. up to n.
So that is what we have seen over here.
Right?
So we know that this is nothing but n into n plus one by two.
So if I have a string of length n then the number of substrings that I have that I can make from that
string would be n into n plus one by two.
And when you simplify this, you will see that you will have an n square term.
Right.
So this is n square plus n by two.
So we can say that the number of substrings will be of the order of n square.
All right.
Now after we have taken into consideration all the possible substrings, we need to identify the substrings
of unique characters.
So for each of the substring that we have identified, we have to do an upper bound of n operations
to traverse it.
So identifying the substrings of unique characters.
So when we reach over here we will have done o of n cube operations.
Right.
So the time complexity will be O of n cube.
And among them we just have to identify the maximum length.
So we clearly can see that this is not an optimal solution.
Let's try to think about a method with which we can do this in a much better time.
Complexity.
Now, you may have already thought about this.
Let's say this is the string which is given to us.
We can just use a simple hash table to store when we encounter a character.
Like for example, we have B over here.
Now as we traverse this string which is given to us when we come to this place, we can see that a B
already was there because we are storing it in a hash table.
So this would be the best way by which we can solve this.
So we are going to store in a hash table whenever we are going to encounter a character, and we are
going to store the index of that character.
Why is that?
So let's say we are we are traversing in this direction.
So we have p q b r s t.
So at this point we have already identified a substring of length six.
Now again we come to B.
Right now at this point we have to move the starting to this character over here.
Because if I continue if I if I take this B then I cannot take this B right.
So I cannot go to the right.
So I have to move my starting point to the next index after what is there over here.
And then I keep counting.
So I have r s t b u v w p.
So all of these can be taken together.
Right.
So this is how we are going to solve this question.
So point number one we are going to store in a hash table whenever we encounter a new character.
And we are going to store the index of that character in the given string.
Now when we encounter a character which already was there previously, we will know because we will
see that that particular key is there in the hash table.
Now, in that case, we will have to decide whether we have to move our start.
Because again, why is there a decision?
For example, we have a P over here right now.
You can see that because we had a B over here, we moved the start to this this place.
So we are only considering strings starting from R.
Now if we see a P just because there was a P earlier, we don't need to move the start to this place,
which is before the place where the current start is.
So that is not required, right?
Because in that case again we'll have two B's in between.
If we are going to take the start from here and something the end is.
Somewhere over here.
All right.
So this is just developing an intuition.
So point number one we are going to store in the hash table whenever we encounter a character.
And when we encounter a character for the second time, we are going to decide whether we need to move
the start pointer or not.
And we will make an operation on the hash table so that we keep track where the particular character
occurred.
Latest in the string which is given to us.
All right.
So this is the intuition.
Now let's just trace the algorithm and see what's happening to develop a good understanding of this
approach.
So again we are going to have a variable start.
So it's going to point at the index zero in the beginning.
And we need a variable.
Let's call it max.
So over here we will initialize it to zero.
And then as we get uh substrings of longer length with unique characters we will just keep updating
this value over here.
And we also need a hash table.
Let's call it scene.
And initially this hash table is going to be empty.
Now let me go ahead and write the indices of this string over here.
All right.
Now to traverse the given string we will need a variable.
And let's call it I.
And I is pointing to zero at this point.
Now we are going to see whether P is there in our hash table.
At the present moment we can see that it is not there.
So we are going to make an entry into our hash table.
The key is going to be p and the value is going to be this index over here which is zero.
Now we can see that we have identified a substring.
This over here which is of length one and length one is greater than zero.
So let's update max to one.
All right.
Now let's move I.
So we move I ahead and I is pointing to one at this point.
Now we have the character Q over here.
Now Q is not there in our hash table.
So let's make an entry Q and the value is going to be one which is this one.
Over here.
Now we have identified a substring p q and the length of this substring is two which is greater than
one.
So let's update max to two.
All right.
Now again, let's move AI forward.
So AI is pointing to two now.
And we have identified a substring PCB.
B is not there in our hash table.
So let's make an entry too.
And we update max to three because this is of length three.
All right, now let's proceed.
We move I ahead.
So I is pointing to are at this point and we can see that this is not there in our hash table.
So let's make an entry.
Ah and three and again we have identified a substring of length four which is greater than three.
So let's update it.
And we have four over here.
And we move ahead.
Now I is pointing to the character S right.
So again we do not have it in our hash table.
So we make this entry S four.
And we have identified a substring of length five.
So we change max to five and we move forward.
So now I is pointing to five.
The character over here is T t is not there in our hash table.
So let's make an entry.
And we update max to six because we have identified this substring which is made up of unique characters.
All right.
Now the fun happens.
Now when we move I, we encounter a character which is already there in our hash table.
Right?
We can see that B two is already there in our hash table, and that is the character at index six.
Now we have to decide whether we need to move the start or not.
So at this point start is actually before occurring before the previous occurrence of B.
So that is why we will have to move start right.
Because if you don't move start, then we will not be able to form a substring of unique characters
because this B will come in between.
Right?
So we should not have this b anymore.
That's why we need to move start now.
How do we check this.
How does the code do this.
We will check whether start is greater or this B this index over here plus one which is three is great
is greater.
So start will be equal to the maximum between the previous value of start and two plus one where this
two over here is the value which we have in our hash table for the key B and that is this two over here.
All right.
So the next index after this two which is the previous occurrence of character b the next index after
this which is two plus one.
That's three.
And start currently is equal to zero which is this.
Over here.
Now in this case we can visually see start is before this two.
Right.
So therefore we have to move start.
And we have checked it by this pseudo code.
Over here we are.
We are checking between start and the value at the key.
The key B which is the character plus one.
So two plus one and start among these two three is greater.
So we have to move start.
So let's move start to three.
So we move start over here.
And you can see that by doing this we have avoided this right.
So we have avoided taking B.
So we can go ahead and check for a longer substring with unique characters.
So let's proceed.
And again B is already there.
So we don't need to make a new entry.
But we have to update this value over here because we want the latest occurrence of B.
And at the same time what about Max.
Now at this point start is over here and I is over here.
So the substring which we have is only of length four.
But this is length six right.
So we don't update max.
Max is still six.
But as we discussed we have to update this 2 to 6 over here.
So six is the latest occurrence of B.
That is why we have to update this.
All right.
Now let's proceed.
We again shift I ahead.
So I is now pointing to index seven.
We have you over here and you is not there in our hash table.
So we make an entry you and seven seven is the index over here.
And let's check the string r s t b u.
This is of length five.
But we have already identified a substring of length six.
So we don't change this.
And we move ahead.
Now I is pointing to index eight and v is not there in our hash table.
So let's make an entry v eight.
And what about the substring.
The substring is of length six.
So that is what we have.
We already have over here.
So we don't update this right.
Again we move forward.
Now we have w w is not there in our hash table.
We make an entry and we change max because now we have identified a substring of length seven.
Right.
So max at this point is equal to seven.
Now again we move I forward and we encounter p.
And we have already encountered P previously.
So we can see that when we look at our hash table, P is already there and the key is p and the value
is zero.
Now again we have to decide whether we need to move start or not.
Now over here we can see that start is already ahead of this.
Right.
So this index is over here.
Now we can see that start is already ahead of it.
So there is no point in moving it back.
Right.
Logically.
So that is what is done by the check that we have put in the code.
We will check whether start is greater or this index plus one is greater.
So we will say that start is equal to max between start and this zero over here plus one.
Now at this point start is equal to three and zero plus one is equal to one.
So among three and one three is greater.
So we don't need to move start right.
And we can see that we have identified a substring of length equal to eight.
So let's update the length.
And we have eight over here.
And we move forward.
All right.
And again remember this over here has to be updated to ten which is the latest occurrence of P.
All right.
Now we move again I forward.
Now at this point we have V and we can see that V is there in our hash table over here.
Right.
So therefore again we have to decide whether we have to move.
Start now in this case this occurrence of V is ahead of what start is currently right.
Therefore yes we have to move it.
And to check this we are going to say start is max between Start and this eight over here, which is
the value currently in our hash table for the key V plus one.
So start is three and eight plus one is equal to nine.
So yes we have to move it to nine.
So we move start to nine.
And then again over here the length of the substring is just three.
So we don't update.
And we keep max at eight itself.
And then we move forward.
And again over here we have to update V to the latest occurrence which is 11.
So this has to be changed to 11.
So this eight has to be changed to 11.
And then we move forward.
So again we have y over here.
It's not there in our hash table.
So we make an entry y 12.
And that is the end right.
So again this length is four which is not greater than eight.
So we stay at eight.
And that gives us the answer.
All right.
And then we just have to return eight.
And that is the answer.
Now let's quickly look at the complexity analysis of this solution that we discussed.
The time complexity of this solution is clearly o of n right.
It's just an order of n where n is the length of the string.
Because we can see that we just had to traverse the given string once.
So we're just iterating through the string.
And for each value of I we are just doing a set of constant time operations, which is things like changing
the start, accessing or updating values from a hash table and comparing the length.
Now all of these are just constant time operations, right?
Again, remember that's the advantage of a hash table, right?
If you have a key you can access or update values in the hash table in constant time.
So we are making use of this property to solve this question in the optimal time complexity.
So we have seen that the time complexity of this solution is O of n.
Now what about the space complexity of this solution?
Now we can say that the space complexity of the solution will depend on the size of our hash table seen.
Right.
So let's try to think about this.
Let's say the given string is of length n.
And let's say m is the number of unique characters which is used in the string.
So therefore we can say that if if m is the number of unique characters used, then the space complexity
will be just m, right?
So the space complexity is of the order of the minimum between n and m, where m is the number of unique
characters used.
Now, if all the characters are unique, then we can say that the space complexity is O of N, so that's
the space complexity.
And again remember that's because the hash table, right?
We are only storing unique characters in our hash table.
So the time complexity is O of n and the space complexity is O of the minimum between n and m.