1
00:00:00,770 --> 00:00:04,760
In this video, let's look at one way of solving this question.

2
00:00:04,760 --> 00:00:10,670
It's a good practice that if you pause this video and before you go ahead and look at the solution that

3
00:00:10,670 --> 00:00:17,360
I provide, try to think through the question and try to get a feeling of how you would attempt this

4
00:00:17,360 --> 00:00:17,990
question.

5
00:00:17,990 --> 00:00:18,560
All right.

6
00:00:18,560 --> 00:00:21,590
Now let's go ahead and look at how we could solve this.

7
00:00:21,590 --> 00:00:28,040
The first method which we discuss over here is the brute force method, which is simple to understand.

8
00:00:28,040 --> 00:00:34,310
And, uh, it's it's very it's probably how a person who does not care about complexity would solve

9
00:00:34,310 --> 00:00:35,030
this question.

10
00:00:35,030 --> 00:00:37,010
But again, it's not the optimal way.

11
00:00:37,010 --> 00:00:38,960
Now let's try to understand this method.

12
00:00:38,960 --> 00:00:41,960
Let's say the given string is this one over here.

13
00:00:41,960 --> 00:00:43,280
And let's index it.

14
00:00:43,280 --> 00:00:46,160
So we have 0123456.

15
00:00:46,160 --> 00:00:48,710
Now we will use two pointers.

16
00:00:48,710 --> 00:00:52,970
The first pointer we will let let it point to the zeroth index.

17
00:00:52,970 --> 00:00:54,260
So let's call it p one.

18
00:00:54,260 --> 00:00:56,390
So it's pointing to the zeroth index.

19
00:00:56,390 --> 00:01:02,690
And then we will use another pointer and traverse the remaining string using this pointer.

20
00:01:02,690 --> 00:01:10,250
And check if this character that is the character at pointer p one, which is a in this case is repeating

21
00:01:10,250 --> 00:01:10,850
or not.

22
00:01:10,850 --> 00:01:14,510
So p two initially let it point over here.

23
00:01:15,110 --> 00:01:16,400
It's not repeating.

24
00:01:16,400 --> 00:01:19,340
Now if it points over here it's not repeating.

25
00:01:19,340 --> 00:01:21,890
If it's pointing over here, it's not repeating.

26
00:01:21,890 --> 00:01:25,190
But when it points over here we can see that it's repeating.

27
00:01:25,190 --> 00:01:28,280
So A is not non-repeating right.

28
00:01:28,280 --> 00:01:31,430
So we have to change the position of pointer one.

29
00:01:31,430 --> 00:01:34,190
Let's point it to the next character over here.

30
00:01:34,190 --> 00:01:37,850
And then we will traverse the remaining string.

31
00:01:37,850 --> 00:01:40,490
Pointer two will initially point over here.

32
00:01:40,490 --> 00:01:42,410
And these are not the same.

33
00:01:42,410 --> 00:01:50,060
And then we will check the remaining string and see whether the value at that pointer one and value

34
00:01:50,060 --> 00:01:52,850
at pointer two is matching or not.

35
00:01:52,850 --> 00:01:55,220
And in this case we will see that it's not matching.

36
00:01:55,220 --> 00:01:56,630
It's matching nowhere.

37
00:01:56,630 --> 00:02:02,720
Now one thing that you should keep in mind over here is notice that we are using both the pointers to

38
00:02:02,720 --> 00:02:04,850
traverse the entire string.

39
00:02:04,850 --> 00:02:10,820
Now, the only thing that we should take care is we should not allow p one to be equal to p two.

40
00:02:10,850 --> 00:02:16,700
If both the pointers are pointing to the same character, then always the character will be equal,

41
00:02:16,700 --> 00:02:17,030
right?

42
00:02:17,030 --> 00:02:23,660
Even in in a case like this a, b, c, d where there is clearly no non repeating character, if p one

43
00:02:23,660 --> 00:02:29,660
points to a and p two points to a, the value at p one and value at p two are equal, right?

44
00:02:29,660 --> 00:02:32,030
So this is not what we should be doing.

45
00:02:32,030 --> 00:02:37,310
So you need to take care that when you write the code you should ensure that p one should not be equal

46
00:02:37,310 --> 00:02:37,970
to p two.

47
00:02:37,970 --> 00:02:42,920
When we make the comparison, whether the value at pointer one and whether the value at pointer two

48
00:02:42,950 --> 00:02:44,060
is equal or not.

49
00:02:44,240 --> 00:02:44,780
All right.

50
00:02:45,260 --> 00:02:52,310
Now when we were checking for uh pointer one on index one we had the value b.

51
00:02:52,310 --> 00:02:55,820
And then we traverse the remaining string using p two.

52
00:02:55,820 --> 00:02:58,790
And we found that b was not repeating anywhere.

53
00:02:58,790 --> 00:03:05,720
Therefore as it was not repeating we have our answer and we can just return one which is the index of

54
00:03:05,720 --> 00:03:07,310
the first non repeating character.

55
00:03:07,310 --> 00:03:11,480
And that's what is asked in the question which is to be returned.

56
00:03:11,480 --> 00:03:11,750
Right.

57
00:03:11,750 --> 00:03:14,030
So we can just return this index over here.

58
00:03:14,030 --> 00:03:18,080
Now let's look at the complexity analysis of this solution.

59
00:03:18,080 --> 00:03:19,340
The brute force method.

60
00:03:19,340 --> 00:03:23,750
Over here we can see that there are time complexity of this solution.

61
00:03:23,750 --> 00:03:25,400
Is O of n square.

62
00:03:25,400 --> 00:03:26,450
Why is that so?

63
00:03:26,450 --> 00:03:32,480
Because when we have a pointer and then for every value of that pointer, we are traversing again through

64
00:03:32,480 --> 00:03:34,670
the entire string which is given over here.

65
00:03:34,670 --> 00:03:34,910
Right.

66
00:03:34,910 --> 00:03:38,180
So this is equivalent to having a nested for loop.

67
00:03:38,180 --> 00:03:38,390
Right.

68
00:03:38,390 --> 00:03:42,080
When we were when when we code this out we will be using a nested for loop.

69
00:03:42,080 --> 00:03:44,930
So that's one way of thinking about it right now.

70
00:03:44,930 --> 00:03:51,470
Another way is like you can just understand that for every value of p one, we are doing n operations.

71
00:03:51,470 --> 00:03:57,380
And let's say this given array or this given string has n characters.

72
00:03:57,590 --> 00:04:02,930
So to traverse the given string one time we will do n operations.

73
00:04:02,930 --> 00:04:10,040
And in each of these n operations to traverse the array again using the second pointer we will do another

74
00:04:10,040 --> 00:04:10,910
n operations.

75
00:04:10,910 --> 00:04:16,220
So that's why the time complexity is n into n which is O of n square.

76
00:04:16,220 --> 00:04:19,340
And to implement this we will be using a nested for loop.

77
00:04:19,340 --> 00:04:23,720
So again a nested for loop gives us a time complexity of O of n square.

78
00:04:23,720 --> 00:04:25,910
Now what about the space complexity?

79
00:04:25,910 --> 00:04:30,440
The space complexity of the brute force method over here is o of one.

80
00:04:30,440 --> 00:04:31,430
Why is that so?

81
00:04:31,430 --> 00:04:34,220
Because we are not using any additional space.

82
00:04:34,220 --> 00:04:36,230
We are not storing anything, right?

83
00:04:36,650 --> 00:04:40,550
In fact, that's one reason why the method is not efficient.

84
00:04:40,550 --> 00:04:46,700
And we are using a lot of, um, runtime while running the algorithm and getting a time complexity of

85
00:04:46,700 --> 00:04:47,690
O of n square.

86
00:04:47,690 --> 00:04:53,300
Now in the next video we will see how we can optimize this solution.