Hi everyone, we have successfully coded the optimal solution for this question.
Now let's take a sample input and walk through the code and see what's happening.
Let's say this is the given string and we are passing it to the function.
Find non-repeating character.
Now the indices of the given string are 01234567.
Right now in this part of the code where we have the first for loop, what we are doing is we are building
the hash table.
Right.
So how is that happening?
Initially I is equal to zero.
When I is equal to zero, we take the character in the given string at the ith index.
That's string of I, and we are checking whether it's there in the hash table.
Initially the hash table is empty, so it's not there.
So if it's not there it goes to the else and it gets inserted into the hash table.
So we are inserting the key as a because this is a and the count as one.
Right.
So we are just inserting the count as one.
Then I becomes one right I becomes one.
And the character over here in the string at index one is B.
It's not.
We are checking whether it's there in the hash table.
It's not there.
So we are inserting it B one.
And again we are coming to a when I is equal to two.
Now at this point a character A is already there in the hash table.
Therefore we are just incrementing the value.
We are passing string I, which is a as the key to the hash table.
We'll get back one and we are incrementing that one by one.
So this one changes to two in this manner by traversing the string.
Once we are building this hash table over here.
So that's what's happening in this part of the code right now in this for loop.
What we are doing is we are again traversing the string.
Initially I is equal to zero right.
So string of I is a.
We are passing the key A to the hash table and we are getting back the value two.
So when I is equal to zero this part over here is equal to two.
And two is not equal to one.
So we are again incrementing I by one.
So when I is equal to one we are getting this two back again.
It's two when I is equal to two when I is equal to two, we are again passing a right.
So when we pass a we get back this two again.
So again we have we don't have one.
So again I is incremented.
Now let me make some space over here.
At this point, when I is equal to three, we are passing capital R.
Right now in our hash table for capital R the value is one right.
So when I is equal to three this part over here is equal to one.
One is equal to one.
So we enter over here right.
We are able to enter over here.
And over here it says return I.
So we will return three.
And that ends this function.
And we get the index of the first non-repeating character.
Now let me make some space over here.
Now let's quickly look at the time and space complexity of this solution.
The time complexity of this solution is O of n right.
We have n operations to make the hash table, and we do n operations over here when we traverse the
string once.
But this is not nested right.
You can notice that this is not nested.
So the total operations in this case will be n plus n.
So we can say that the time complexity is O of two n.
And because two is a constant, we can just remove it and we get the time complexity as O of n.
Now the space complexity is O of one, right?
Why is that so?
Because in the question it's given that the string which will be given to us will only consist of small
letters, uppercase letters, and integers 0 to 9.
Now, in the case of small letters in the English alphabet, there are 26 possibilities.
For uppercase letters, there are 26 possibilities, and for integers 0 to 9, ten possibilities.
So the total possibilities is just 26 plus 26 plus ten.
Right?
So that's actually only 62 possibilities.
So we can say that the space complexity is O of 62, which is the same as saying that the space complexity
is O of one, which is constant space.
Because this is just a constant right now.
If this was not given, if it was not mentioned that the string would consist only of these characters,
then the space complexity would have been O of n.