1
00:00:00,860 --> 00:00:01,790
Hi everyone.

2
00:00:01,790 --> 00:00:05,180
Let's now code together the third method that we discussed.

3
00:00:05,210 --> 00:00:07,460
Now for this we will write a function.

4
00:00:07,460 --> 00:00:09,590
Let's call it is palindrome check.

5
00:00:11,890 --> 00:00:14,830
And this function takes in a string.

6
00:00:15,370 --> 00:00:19,060
Now what we are going to do is we are going to initialize two pointers.

7
00:00:19,090 --> 00:00:21,370
Now let the first pointer be I.

8
00:00:21,370 --> 00:00:26,920
And that's set to zero which is the beginning of the input string, the index of the beginning right.

9
00:00:26,920 --> 00:00:34,030
And the second index let's call it j and we will initialize it to two string dot length minus one.

10
00:00:34,030 --> 00:00:38,260
So this is the index of the last character of the input string.

11
00:00:38,260 --> 00:00:40,690
Now we are going to run a loop.

12
00:00:40,690 --> 00:00:44,020
And this will go on till I less than equal to J.

13
00:00:44,140 --> 00:00:44,560
Right.

14
00:00:44,560 --> 00:00:47,170
So we have seen the two cases in the discussion.

15
00:00:47,170 --> 00:00:51,220
If the length of the input string is an even number.

16
00:00:51,220 --> 00:00:53,440
So let's just quickly see that over here.

17
00:00:53,440 --> 00:00:57,880
Let's say the input string is a b a b b a right.

18
00:00:57,880 --> 00:00:59,860
So this is of length four.

19
00:00:59,860 --> 00:01:03,130
And the other case is let's say it's a b c b a.

20
00:01:03,250 --> 00:01:11,770
Now over here initially I will be a and j will be a, then I will be B and j will be B, and then afterwards

21
00:01:11,830 --> 00:01:17,050
when we do I plus plus and j minus minus, you can see that I will become greater than j.

22
00:01:17,050 --> 00:01:18,760
So we need to stop at this point.

23
00:01:18,760 --> 00:01:21,130
So that's why we have I less than J.

24
00:01:21,130 --> 00:01:27,100
And in the case of an a string with length odd number like for over here the length of the string is

25
00:01:27,100 --> 00:01:27,550
five.

26
00:01:27,550 --> 00:01:32,980
So in this case initially I will be at this pointer like at zero right.

27
00:01:32,980 --> 00:01:35,440
And J will be over here pointing to this character.

28
00:01:35,440 --> 00:01:41,110
Then I will point to this character and J will point to this character, and then both will point to

29
00:01:41,110 --> 00:01:43,030
the middle character or it got deleted.

30
00:01:43,030 --> 00:01:43,540
Okay.

31
00:01:43,540 --> 00:01:48,730
So both will point to the middle character C and afterwards we need to stop right?

32
00:01:48,730 --> 00:01:53,650
When they change the uh, when it becomes I will become greater than J.

33
00:01:53,650 --> 00:01:58,510
So we could also write, while not I greater than J, it's both the same.

34
00:01:58,510 --> 00:02:03,640
While I less than equal to j is the same as while I not greater than j, so it's the same.

35
00:02:03,640 --> 00:02:07,480
So this will keep repeating while this is true.

36
00:02:07,480 --> 00:02:07,960
All right.

37
00:02:07,960 --> 00:02:10,300
Now when this is true, what are we going to do.

38
00:02:10,300 --> 00:02:14,650
We are going to compare the character at the ith and jth index.

39
00:02:14,650 --> 00:02:20,230
So string I if this is not equal to string of j.

40
00:02:21,380 --> 00:02:25,340
So if these are not equal, then it's definitely not a palindrome.

41
00:02:25,340 --> 00:02:25,520
Right.

42
00:02:25,520 --> 00:02:27,650
So we can just return false.

43
00:02:28,190 --> 00:02:29,810
So we come out of the function.

44
00:02:29,810 --> 00:02:33,260
Now if this is true if these are true right.

45
00:02:33,260 --> 00:02:37,340
For example let's say we have some characters in between.

46
00:02:37,340 --> 00:02:43,430
And the first one is a the character of the first character is a, and let's say the last character

47
00:02:43,430 --> 00:02:43,850
is a.

48
00:02:43,880 --> 00:02:46,760
So at this point we see that both of them are equal.

49
00:02:46,760 --> 00:02:48,260
So what do we do.

50
00:02:48,290 --> 00:02:51,320
We need to increment I and we need to decrement j.

51
00:02:51,320 --> 00:02:51,710
Right.

52
00:02:51,710 --> 00:02:52,790
So let's do that.

53
00:02:52,790 --> 00:02:59,000
So if it's not true that that is if these two characters are true then what do we do.

54
00:02:59,030 --> 00:03:05,870
We have an else part over here in this part what we do is we increment I so that this pointer, whatever

55
00:03:05,870 --> 00:03:08,450
was pointing over here goes to the right.

56
00:03:08,450 --> 00:03:10,580
And we decrement j right.

57
00:03:10,580 --> 00:03:13,940
So that whatever was pointing over here goes to the left.

58
00:03:13,940 --> 00:03:15,350
So j minus minus.

59
00:03:15,410 --> 00:03:17,330
And then that's it.

60
00:03:17,330 --> 00:03:22,760
So if we come out of this loop without returning false that means that it's true.

61
00:03:22,760 --> 00:03:22,970
Right.

62
00:03:22,970 --> 00:03:26,630
So we return true over here and we have our function.

63
00:03:26,630 --> 00:03:28,280
Now let's test it.

64
00:03:28,280 --> 00:03:32,060
Let's call our function and check whether it's working.

65
00:03:32,060 --> 00:03:37,340
So to this function let me pass the string ABC.

66
00:03:37,340 --> 00:03:38,570
So this is ABC.

67
00:03:38,570 --> 00:03:41,180
Let's now see what we get when we run this.

68
00:03:41,180 --> 00:03:44,360
When we run this we'll get false because this is not a palindrome.

69
00:03:44,360 --> 00:03:48,890
Right now if we have BA over here we get true because this is a palindrome.

70
00:03:48,890 --> 00:03:51,830
Again, if I have AA, I get true.

71
00:03:51,830 --> 00:03:55,730
If I have a A, I get false because this is not a palindrome.

72
00:03:55,730 --> 00:03:57,590
So yes, this solution is working.

73
00:03:57,590 --> 00:04:04,220
And you can see that this is a solution which runs in a time complexity of O of N, right.

74
00:04:04,220 --> 00:04:11,420
So we can see that we just have this loop over here and we are traversing the given string only once.

75
00:04:11,420 --> 00:04:11,840
Right.

76
00:04:11,840 --> 00:04:13,610
In fact it's o of n by two.

77
00:04:13,610 --> 00:04:13,820
Right.

78
00:04:13,820 --> 00:04:15,350
Because we're going from both the sides.

79
00:04:15,350 --> 00:04:17,030
But then one by two is a constant.

80
00:04:17,030 --> 00:04:18,590
So we leave that right.

81
00:04:18,590 --> 00:04:20,570
So the time we can just ignore that.

82
00:04:20,570 --> 00:04:26,060
So the time complexity of this solution is O of n and the space complexity is O of one.

83
00:04:26,060 --> 00:04:26,270
Right.

84
00:04:26,270 --> 00:04:31,880
We are not creating a new array or a new string like we saw in the previous solutions.

85
00:04:31,880 --> 00:04:34,970
So the space complexity of the solution is O of one.