1
00:00:00,550 --> 00:00:01,450
Hi everyone.

2
00:00:01,450 --> 00:00:05,230
Let's discuss various methods by which we can solve this question.

3
00:00:05,230 --> 00:00:07,870
Now let's say that the input string is Malayalam.

4
00:00:07,870 --> 00:00:08,290
All right.

5
00:00:08,290 --> 00:00:09,730
So this is a palindrome.

6
00:00:09,730 --> 00:00:11,650
It reads the same forward and backward.

7
00:00:11,650 --> 00:00:14,830
Now we'll see three methods by which we can solve this.

8
00:00:14,830 --> 00:00:19,480
Now the first method would be that we could create a new string starting from the end.

9
00:00:19,480 --> 00:00:19,750
Right.

10
00:00:19,750 --> 00:00:21,100
We can create a new string.

11
00:00:21,100 --> 00:00:22,840
Initially this string will be empty.

12
00:00:22,840 --> 00:00:28,810
And then we'll take one character by character starting from the end, and we'll append it to the new

13
00:00:28,810 --> 00:00:29,260
string.

14
00:00:29,260 --> 00:00:33,280
And finally, we'll check whether the new string and the given string is the same.

15
00:00:33,280 --> 00:00:36,370
If they are the same, then we return true, else we return false.

16
00:00:36,370 --> 00:00:38,920
So this is one way we can solve this.

17
00:00:38,920 --> 00:00:41,080
Now this is not an optimal solution.

18
00:00:41,080 --> 00:00:44,830
We'll see in in the discussion why this is not optimal.

19
00:00:44,830 --> 00:00:49,090
Now another solution could be that we create an array instead of a new string.

20
00:00:49,090 --> 00:00:55,180
We create initially an array and we take character by character of the given string from the end.

21
00:00:55,180 --> 00:01:00,910
So initially we take character M, then we take character A, etc. and we insert it into the array.

22
00:01:00,910 --> 00:01:06,460
So that would be m, comma a, etc. and then we join these characters to form a string.

23
00:01:06,460 --> 00:01:08,980
And then we compare this string and the given string.

24
00:01:08,980 --> 00:01:10,900
So if they are the same we return true.

25
00:01:10,900 --> 00:01:13,030
If they are not the same, we return false.

26
00:01:13,030 --> 00:01:14,260
So this is another way.

27
00:01:14,260 --> 00:01:16,690
Now this is better than the first method.

28
00:01:16,690 --> 00:01:18,940
And we'll see why that is so.

29
00:01:18,940 --> 00:01:20,680
But it is not the best method.

30
00:01:20,680 --> 00:01:26,530
And finally in this section we'll see a third method where we use two pointers.

31
00:01:27,530 --> 00:01:29,450
And one pointer would be at the beginning.

32
00:01:29,450 --> 00:01:30,500
That's over here.

33
00:01:30,500 --> 00:01:32,690
And the other pointer would be at the end.

34
00:01:32,690 --> 00:01:35,510
And we'll check whether these two have the same character.

35
00:01:35,510 --> 00:01:40,340
And if so, we will increment the beginning pointer to this place over here.

36
00:01:40,340 --> 00:01:43,970
And we'll decrement the pointer at the end to this place.

37
00:01:43,970 --> 00:01:46,010
And we'll keep comparing if they are the same.

38
00:01:46,010 --> 00:01:52,190
So if throughout we get that these characters are the same, we return true, else we break and we return

39
00:01:52,190 --> 00:01:52,640
false.

40
00:01:52,640 --> 00:01:55,160
So these are the three methods that we will discuss.

41
00:01:55,160 --> 00:01:59,930
Now let's go ahead and see the first method where we create a new string.

42
00:01:59,930 --> 00:02:00,500
All right.

43
00:02:00,500 --> 00:02:04,880
So let's say that the input given to us is a b c b a.

44
00:02:05,090 --> 00:02:09,710
Now let's initially create a new string so we can give it any name.

45
00:02:09,710 --> 00:02:12,170
Let's say we call it to check.

46
00:02:12,170 --> 00:02:12,590
All right.

47
00:02:12,590 --> 00:02:14,990
So initially this is an empty string.

48
00:02:14,990 --> 00:02:16,700
Now we have a pointer.

49
00:02:16,700 --> 00:02:19,640
And it's pointing to the end of the given string.

50
00:02:19,640 --> 00:02:22,310
And we take the character at this index.

51
00:02:22,310 --> 00:02:24,680
So this is 01234.

52
00:02:24,680 --> 00:02:28,520
So we take the character at index four which is string length minus one.

53
00:02:28,520 --> 00:02:28,760
Right.

54
00:02:28,760 --> 00:02:32,240
So we take this character and we append it to the.

55
00:02:33,040 --> 00:02:35,200
String which we defined over here to check.

56
00:02:35,200 --> 00:02:36,820
So two check becomes a.

57
00:02:36,820 --> 00:02:38,170
Now it's just a.

58
00:02:38,170 --> 00:02:42,520
Then we move the pointer to the left left right.

59
00:02:42,520 --> 00:02:44,020
So the pointer is pointing over here.

60
00:02:44,020 --> 00:02:45,670
Now that is two index three.

61
00:02:45,670 --> 00:02:48,460
We take the character and we append it to two check.

62
00:02:48,460 --> 00:02:50,020
So two check becomes a b.

63
00:02:50,020 --> 00:02:51,430
So this is string okay.

64
00:02:51,430 --> 00:02:53,080
So again we do the same thing.

65
00:02:53,080 --> 00:02:57,880
We move the pointer to the left and take the character C and append it to two.

66
00:02:57,880 --> 00:02:58,300
Check.

67
00:02:58,300 --> 00:02:59,290
We do it again.

68
00:02:59,290 --> 00:03:01,240
We take the character B and append it to two.

69
00:03:01,240 --> 00:03:01,630
Check.

70
00:03:01,630 --> 00:03:02,800
And we do it again.

71
00:03:02,800 --> 00:03:05,770
We take the character A and append it to two check.

72
00:03:05,770 --> 00:03:07,990
So now we have a new string.

73
00:03:07,990 --> 00:03:10,660
Now we just need to compare these two strings.

74
00:03:10,660 --> 00:03:16,180
Now if they are the same, we can return true because they read the same forward and backward.

75
00:03:16,180 --> 00:03:18,220
And that's the definition of a palindrome.

76
00:03:18,220 --> 00:03:23,830
Now if these two strings are not the same, then we can return false and we have our solution.

77
00:03:23,830 --> 00:03:28,030
Now let's quickly look at the complexity analysis of this solution.

78
00:03:28,030 --> 00:03:32,920
Now the time complexity of this solution will be O of n square.

79
00:03:32,920 --> 00:03:33,700
Why is that.

80
00:03:33,700 --> 00:03:39,280
So you can see that we are doing appending operation on a string right now.

81
00:03:39,280 --> 00:03:43,180
Strings in languages such as JavaScript are immutable.

82
00:03:43,180 --> 00:03:49,780
So when you append something to a string in JavaScript, you are actually traversing the string and

83
00:03:49,780 --> 00:03:54,580
you are creating a new copy of the string and appending the character which you are appending, right?

84
00:03:54,580 --> 00:03:58,900
So this is actually an operation n or order of n operation.

85
00:03:58,900 --> 00:04:02,680
So over here we are doing this every time we have a character.

86
00:04:02,680 --> 00:04:02,920
Right.

87
00:04:02,920 --> 00:04:07,750
So if you have n characters so let's say the string is of length n.

88
00:04:07,750 --> 00:04:13,690
And for each of these when we append we are doing an o of n operation.

89
00:04:13,690 --> 00:04:19,540
So that's why the time complexity over here is n into n, which is o of n square.

90
00:04:20,600 --> 00:04:26,330
So every time we are creating a new string, because strings are immutable in languages like JavaScript.

91
00:04:26,690 --> 00:04:32,000
Remember when we are appending to the string, what's actually happening is we are iterating through

92
00:04:32,000 --> 00:04:36,590
all the characters, copying it, creating a new copy, and adding the new character.

93
00:04:36,590 --> 00:04:40,400
So that's why the time complexity over here is O of n square.

94
00:04:40,430 --> 00:04:42,590
Now what about the space complexity?

95
00:04:42,590 --> 00:04:45,830
The space complexity of this solution is O of N.

96
00:04:45,830 --> 00:04:46,760
Why is that so?

97
00:04:46,760 --> 00:04:49,730
Because we are creating a new string over here, right.

98
00:04:49,730 --> 00:04:51,980
Which is of length n also.

99
00:04:51,980 --> 00:04:54,800
So the space complexity is O of n.