1
00:00:00,710 --> 00:00:01,670
Hi everyone!

2
00:00:01,670 --> 00:00:06,200
So we have successfully coded the brute force solution of the given question.

3
00:00:06,200 --> 00:00:12,590
Now let's take a simple string and walk through the code that we have written and see what's happening.

4
00:00:12,590 --> 00:00:13,070
Now.

5
00:00:13,070 --> 00:00:17,510
The indices of the various characters of the given string are these 0 to 7.

6
00:00:17,510 --> 00:00:22,460
Right now let's say this function has been called and this string is passed to this function.

7
00:00:22,460 --> 00:00:24,590
Now over here we have declared repeat.

8
00:00:24,590 --> 00:00:26,510
And then we have this for loop.

9
00:00:26,510 --> 00:00:30,260
When we enter this for loop initially I is equal to zero right.

10
00:00:30,260 --> 00:00:31,460
And repeat.

11
00:00:31,460 --> 00:00:33,620
The value of repeat is set to false.

12
00:00:33,800 --> 00:00:36,950
And then we have the nested for loop over here.

13
00:00:36,950 --> 00:00:39,530
And the value of j is initially zero.

14
00:00:39,530 --> 00:00:42,410
And we are going to keep compare the.

15
00:00:43,280 --> 00:00:48,920
Character in the given string at the ith index and at the jth index.

16
00:00:48,920 --> 00:00:51,290
So that's what we're doing over here, right.

17
00:00:51,380 --> 00:00:52,790
That's happening over here.

18
00:00:53,120 --> 00:00:55,160
We're checking whether these two are equal.

19
00:00:55,160 --> 00:00:56,960
And I should not be equal to J.

20
00:00:56,960 --> 00:00:59,150
So in this case I is zero and j is zero.

21
00:00:59,150 --> 00:01:01,070
So it will not enter over here.

22
00:01:01,070 --> 00:01:02,810
And j will be incremented.

23
00:01:02,810 --> 00:01:11,480
Now when j is equal to one we are going to check a and b right string at zero is uh a and string at

24
00:01:11,480 --> 00:01:12,740
one is b.

25
00:01:12,770 --> 00:01:14,480
So when j is equal to one.

26
00:01:14,480 --> 00:01:16,820
Also we are not going to enter over here.

27
00:01:16,820 --> 00:01:21,980
Now when j is equal to two J is over here pointing over here and I is over here.

28
00:01:21,980 --> 00:01:26,480
And these two are equal right string at zero and string at two.

29
00:01:26,480 --> 00:01:27,380
Both are a.

30
00:01:27,380 --> 00:01:28,340
So these are equal.

31
00:01:28,340 --> 00:01:30,650
So we enter in over here.

32
00:01:30,650 --> 00:01:33,200
And repeat is set to true right.

33
00:01:33,200 --> 00:01:34,760
So repeat is set to true.

34
00:01:34,760 --> 00:01:44,150
Now when we come out of this for loop right when we have done all the iterations for J012 up to uh seven,

35
00:01:44,150 --> 00:01:47,630
right up to uh seven, because the length over here is eight.

36
00:01:47,630 --> 00:01:54,050
So this will keep going up to seven now when we come out of it, because we were able to enter in over

37
00:01:54,050 --> 00:01:56,180
here, the value of repeat is true.

38
00:01:56,180 --> 00:01:56,540
Right.

39
00:01:56,540 --> 00:01:59,270
So we are going to check this whether repeat is false.

40
00:01:59,270 --> 00:02:01,580
But the value of repeat is true.

41
00:02:01,580 --> 00:02:04,100
So I'm just writing R for repeat in this case.

42
00:02:04,100 --> 00:02:05,570
So repeat is true.

43
00:02:05,570 --> 00:02:07,220
So it will not return anything.

44
00:02:07,220 --> 00:02:12,200
And the value of I will be incremented which is happening over here in this for loop.

45
00:02:12,200 --> 00:02:12,560
Right.

46
00:02:12,560 --> 00:02:14,660
So I will be set to one.

47
00:02:14,660 --> 00:02:17,720
And again we are going to set repeat to false.

48
00:02:17,720 --> 00:02:20,300
And we will keep traversing the array with j.

49
00:02:20,300 --> 00:02:23,540
So j will be zero, one, two, three etc..

50
00:02:23,540 --> 00:02:27,740
So when I is one so I is pointing over here.

51
00:02:27,740 --> 00:02:28,940
So we have the value b.

52
00:02:28,940 --> 00:02:33,860
And then we are going to check all of these except j should not be one itself.

53
00:02:33,860 --> 00:02:37,310
So this will fail because we have this condition written over here.

54
00:02:37,310 --> 00:02:37,790
Right.

55
00:02:38,180 --> 00:02:39,380
So it will not go inside.

56
00:02:39,380 --> 00:02:48,230
So in these cases a again we get a at at zero we get a at two we get a at three we get R and at four

57
00:02:48,230 --> 00:02:49,280
we get B.

58
00:02:49,670 --> 00:02:52,310
And over here the values are same.

59
00:02:52,310 --> 00:02:56,000
So string of one and string of four.

60
00:02:56,030 --> 00:02:56,930
These are equal.

61
00:02:56,930 --> 00:03:00,590
So again repeat is set to true at this point also.

62
00:03:00,590 --> 00:03:06,620
And then when we keep the remaining values for j we go ahead for five six and seven.

63
00:03:06,620 --> 00:03:09,050
And we come out of this for loop this one.

64
00:03:09,050 --> 00:03:11,540
And we check over here whether repeat is false.

65
00:03:11,540 --> 00:03:14,330
But at this point repeat has been set to true.

66
00:03:14,330 --> 00:03:16,490
So it does not enter over here.

67
00:03:16,490 --> 00:03:19,790
And again I is incremented and I becomes two.

68
00:03:19,790 --> 00:03:23,240
And at this point when J is zero itself right.

69
00:03:23,240 --> 00:03:24,590
This is where I is.

70
00:03:24,590 --> 00:03:28,010
When j is zero itself, the values are the same.

71
00:03:28,010 --> 00:03:31,400
So repeat is set to true and it keeps going till seven.

72
00:03:31,400 --> 00:03:34,070
And when we come to this part repeat is again true.

73
00:03:34,070 --> 00:03:35,840
So nothing is returned.

74
00:03:35,840 --> 00:03:38,420
Now I is incremented to three.

75
00:03:38,840 --> 00:03:45,170
Now at this point, when we traverse the remaining part of the array, we can see that in no place the

76
00:03:45,170 --> 00:03:46,820
values are equal.

77
00:03:46,820 --> 00:03:50,780
Therefore, repeat stays false, repeat stays false.

78
00:03:50,780 --> 00:03:56,510
And when we come out of this for loop and have this check over here, whether repeat is false.

79
00:03:56,510 --> 00:03:58,670
Yes, repeat is false in this case.

80
00:03:58,670 --> 00:04:02,360
Therefore, we return this I which is equal to three.

81
00:04:02,360 --> 00:04:03,380
So we return three.

82
00:04:03,380 --> 00:04:05,330
And that's the answer to this question.

83
00:04:05,330 --> 00:04:07,730
So that's what's happening in the code that we have written.

84
00:04:07,730 --> 00:04:11,870
Now let's quickly look at the time and space complexity of our code.

85
00:04:11,870 --> 00:04:15,920
We have seen that the time complexity of this solution is O of n square.

86
00:04:15,920 --> 00:04:18,830
Again, that's because we have a nested for loop over here.

87
00:04:18,830 --> 00:04:19,370
Right.

88
00:04:19,370 --> 00:04:23,540
So in this case in the first for loop we are doing n operations.

89
00:04:23,540 --> 00:04:30,440
And for each one operation of these n we are doing again an operations when we have the second for loop.

90
00:04:30,440 --> 00:04:36,560
That's why the time complexity is n into n which is n square or o of n square.

91
00:04:36,560 --> 00:04:38,630
And what about the space complexity?

92
00:04:38,630 --> 00:04:41,240
We are not storing anything new over here, right?

93
00:04:41,240 --> 00:04:42,830
We are not storing anything new.

94
00:04:42,830 --> 00:04:48,920
And hence this algorithm runs in constant space or O of one space complexity.