Hi everyone.
In this video let's try to code together the optimal solution which we discussed in the previous video.
Now to start with, let's create a function and let's call it find non-repeating character.
And this function takes in a string.
All right.
Now what we are going to do is we are going to create a hash table, and we will traverse the string
once and we will insert into the hash table each character and the count, or how many times that particular
character is, is occurring in the string.
Right.
And afterwards we will traverse the string again and find the first character which is coming in the
string, which has only a count of one in the hash table which we created.
So let's start by creating a hash table.
Let me call it hash table itself.
So this is a hash table.
It's an empty hash table at this point.
Now let's traverse the given string and let's fill into this hash table the characters and the count,
or how many times each particular character is occurring in this input string.
So for this let's say let I is equal to zero I less than string dot length.
I plus, plus.
Now we are going to check if string.
If the character at the ith index in the string is there in the hash table or not.
So if string I.
In hash table.
So if it's there, what we'll do is we'll increment the value.
So over here string I is the key.
So we are checking the hash table.
If this key is there in the hash table.
If it's there we will increment the count by one.
So hash table.
String I.
Plus plus.
So we are incrementing the count by one.
Now, if it is not there, what we do is we will insert the key value pair into the hash table, and
the key will be the character, and the value will be one because it's not there.
So it's being inserted for the first time.
So we say hash table.
At a string I.
That's the key.
And we are giving the value one.
All right.
So at the end of this for loop we will have created the hash table.
And in the hash table let's say for an for an example let's take a uh the string as a b b d.
Now at the end of this for loop, which we just now have written, the hash table will have the values
a and the count is one for b, the count is two, and for d the count is one.
So this is what will be there in the hash table at the end of this for loop.
Now what we need to do is we will traverse the given string again.
So for let I is equal to zero I less than string.
Dot length.
I plus plus.
And we are going to check whether the count for the character string at the string I the character at
the ith index in the given string.
If the count for that string for that character in the hash table which we have made is one or not.
So that's what we're going to check.
So if hash table.
String I.
Equal to one.
So that's what you are checking.
Now, if this is true, then we have found the first non-repeating character.
And we just need to return the index where this is happening.
So let me change this a bit.
So let's say I write one more a over here.
So that over here the count would be two.
So what will happen in this case is first I will be zero.
And that's a so string of I will be a and we will check in the hash table.
So the count is two.
So this will not return.
It will it will be false.
It will not go inside again I will be incremented.
We'll get to be right.
And the value for b is two again I is incremented again we get to be.
The value for b is two.
Again the I the value of I is incremented and we get two d.
Now in this case d will have the count one.
So hash table at d is will be equal to one.
Therefore we will return the index of d.
In this case that's 0123.
So that's what's happening over here.
Now if this has happened and we were not able to return anything.
So there is no non-repeating character in this case we just need to return null, which is the clarification
that we got from the interviewer.
All right.
So let's test our code now for this.
Let's write a test case.
Let's say a is equal to.
Let's take it as one A, two a and one again.
So in this case two is the first non-repeating character.
Now let's pass it and console.log this.
So let's pass A to our function find non-repeating character and we pass A to it.
All right.
So let's now see what's happening.
So we are going to run it now.
And we get the value 2012 which is the correct index of two.
Now what if I add another two over here and run it again.
So I get null.
So we have reached over here.
So there is no non-repeating character.
What if I add let's say capital F to this.
And again I run it I get six.
So 0123456.
That's the index of capital F.
What if I add another capital F.
And let's say I add a small G and a capital G and I run it, I get eight which is the index where small
g occurs.
And as we have clarified from from the interviewer, we are not considering small G and capital G to
be the same character.
So yes, our algorithm is working fine.
Now let's take another test case and walk through this once more and take a relook at the code that
we have written.