In this video, let's look at one way of solving this question.
It's a good practice that if you pause this video and before you go ahead and look at the solution that
I provide, try to think through the question and try to get a feeling of how you would attempt this
question.
All right.
Now let's go ahead and look at how we could solve this.
The first method which we discuss over here is the brute force method, which is simple to understand.
And, uh, it's it's very it's probably how a person who does not care about complexity would solve
this question.
But again, it's not the optimal way.
Now let's try to understand this method.
Let's say the given string is this one over here.
And let's index it.
So we have 0123456.
Now we will use two pointers.
The first pointer we will let let it point to the zeroth index.
So let's call it p one.
So it's pointing to the zeroth index.
And then we will use another pointer and traverse the remaining string using this pointer.
And check if this character that is the character at pointer p one, which is a in this case is repeating
or not.
So p two initially let it point over here.
It's not repeating.
Now if it points over here it's not repeating.
If it's pointing over here, it's not repeating.
But when it points over here we can see that it's repeating.
So A is not non-repeating right.
So we have to change the position of pointer one.
Let's point it to the next character over here.
And then we will traverse the remaining string.
Pointer two will initially point over here.
And these are not the same.
And then we will check the remaining string and see whether the value at that pointer one and value
at pointer two is matching or not.
And in this case we will see that it's not matching.
It's matching nowhere.
Now one thing that you should keep in mind over here is notice that we are using both the pointers to
traverse the entire string.
Now, the only thing that we should take care is we should not allow p one to be equal to p two.
If both the pointers are pointing to the same character, then always the character will be equal,
right?
Even in in a case like this a, b, c, d where there is clearly no non repeating character, if p one
points to a and p two points to a, the value at p one and value at p two are equal, right?
So this is not what we should be doing.
So you need to take care that when you write the code you should ensure that p one should not be equal
to p two.
When we make the comparison, whether the value at pointer one and whether the value at pointer two
is equal or not.
All right.
Now when we were checking for uh pointer one on index one we had the value b.
And then we traverse the remaining string using p two.
And we found that b was not repeating anywhere.
Therefore as it was not repeating we have our answer and we can just return one which is the index of
the first non repeating character.
And that's what is asked in the question which is to be returned.
Right.
So we can just return this index over here.
Now let's look at the complexity analysis of this solution.
The brute force method.
Over here we can see that there are time complexity of this solution.
Is O of n square.
Why is that so?
Because when we have a pointer and then for every value of that pointer, we are traversing again through
the entire string which is given over here.
Right.
So this is equivalent to having a nested for loop.
Right.
When we were when when we code this out we will be using a nested for loop.
So that's one way of thinking about it right now.
Another way is like you can just understand that for every value of p one, we are doing n operations.
And let's say this given array or this given string has n characters.
So to traverse the given string one time we will do n operations.
And in each of these n operations to traverse the array again using the second pointer we will do another
n operations.
So that's why the time complexity is n into n which is O of n square.
And to implement this we will be using a nested for loop.
So again a nested for loop gives us a time complexity of O of n square.
Now what about the space complexity?
The space complexity of the brute force method over here is o of one.
Why is that so?
Because we are not using any additional space.
We are not storing anything, right?
In fact, that's one reason why the method is not efficient.
And we are using a lot of, um, runtime while running the algorithm and getting a time complexity of
O of n square.
Now in the next video we will see how we can optimize this solution.