Hi everyone.
In this video, let's see how to solve this question in a more optimal manner using a hash table.
Now in the previous solution in the brute force method, the problem why we got a time complexity of
O of n square was for every iteration, for every operation in the first for loop, we again looped
through the array again, right?
So let's try to avoid that using a hash table by storing values into a hash table.
So that's what we are trying.
That's what we are trying to do over here.
Now let's say that the given string is this one over here.
Now let's make an empty hash table at the beginning.
Now what we are going to do is we will first once traverse the given string from this zero to the length.
Right.
So 0123456.
These are the indices.
So we'll go from 0 to 6.
And we will fill the hash table with the characters and the counts.
All right.
So initially the pointer would be over here.
And we will see whether this character A is in the hash table.
Now initially it was empty so it was not there.
So we will enter a into the hash table and we will set the counter or the value to one at this point.
Right.
So this is the key and this is the value.
Now we will set it to one.
Now we will move the pointer from here here to here.
So the pointer is over here.
Now we will check is B in the hash table.
It's not there.
So let's enter B and we set the counter to one.
Now again we move the count the count the pointer over here.
And the pointer is now here.
We will check if capital A is in our hash table.
It's not there.
So we enter it into our hash table and the count is set to one.
Again we will move the pointer to the next character which is again capital A, and because it's already
there in the hash table, we won't insert it again, but rather we will increment this value by one
and we will change 1 to 2.
Now we will again do this with the next character.
One is not there.
So let's insert one and the counter is one.
And again we check for small a.
It's already there.
So we change it from 1 to 2.
And for C it's not there.
So we insert it into our hash table.
So for this we have traversed our string the given string one time.
And we have formed this hash table.
All right.
Now what we will do is we will traverse the given string again one more time.
And we will check which character has a count one as per the hash table that we have made over here.
All right.
So let's look at that.
Now again we have our indices over here.
Now when we are over here we are going to check what is the count for the value a in our hash table.
Now we are definitely sure it's going to be there because we just now traverse the whole string and
made this hash table.
Now we are going to pass the key.
The key is going to be a when we are over here right.
The pointer is over here.
The key is going to be a.
And the value that we get back is two.
Right.
So the value over here is two.
So we move forward.
We are actually looking for a case where when we pass a particular character we should be getting a
value of one from our hash table.
So when we pass the next uh character which is b in this case, when we pass it to the hash table,
we will get back one over here.
Right.
So we are getting one over here.
That means in the given string the character B occurs only one time.
And we have our answer.
And we just need to return the index one.
So that's the answer.
And we were able to do it in a much better time complexity.
Let's look at it now.
Now what's the time complexity over here.
We can see that we had to do N operations to make this hash table.
And again n operations to traverse the string.
Right.
So the time complexity net is O of n.
Why is that.
So again that's n operations over here to make the hash table and n operations to traverse the string
the second time.
Right.
So that's n plus n which is equal to two n.
But again we can just avoid a constant.
Therefore the time complexity of this solution is just O of n.
So this is much better than the time complexity of the brute force solution which was O of n square.
Now what about the space complexity here?
It is a bit tricky.
Now the space complexity of this solution is also o of one.
Now you.
When you say this to the interviewer, you need to clarify why.
Now in the question, it's given that the input string is only made up of lowercase English letters,
uppercase uppercase English letters, and integers 0 to 9.
All right.
So in the case of lowercase, a maximum of 26 characters is possible in the case of uppercase English
letters max.
Of 26 characters is possible, and in the case of integers 0 to 9, that's a maximum of ten characters,
right?
So the maximum possible number of characters, unique characters, which can be there in the string
which we are given is 26 plus 26 plus ten, which is equal to 62.
Now, if we say that the space complexity is O of 62, that's the same as O of one, because this is
just a constant, right?
So that's why we can say that the space complexity of this algorithm is O of one, which is constant
space.