1 00:00:00,710 --> 00:00:01,580 Hi everyone. 2 00:00:01,580 --> 00:00:04,850 Let's now discuss the second method to solve this question. 3 00:00:04,850 --> 00:00:09,560 We have seen that when we created a new empty string, right? 4 00:00:09,560 --> 00:00:14,840 And then we kept on appending the characters to it from the back we went in this direction. 5 00:00:14,840 --> 00:00:16,130 This is the given string. 6 00:00:16,130 --> 00:00:22,940 It had a time complexity of O of n square, because appending to a string is not a constant time operation, 7 00:00:22,940 --> 00:00:24,320 it's a o of n operation. 8 00:00:24,320 --> 00:00:24,590 Right. 9 00:00:24,590 --> 00:00:25,520 So we've seen that. 10 00:00:25,520 --> 00:00:27,350 So that's why this was not efficient. 11 00:00:27,350 --> 00:00:30,860 So let's make a slight tweak to method one. 12 00:00:30,860 --> 00:00:37,010 And instead of having initially an empty string let's have an empty array over here. 13 00:00:37,010 --> 00:00:37,610 All right. 14 00:00:37,610 --> 00:00:44,210 Now instead of appending we will keep pushing the characters from the end of the given string. 15 00:00:44,210 --> 00:00:49,730 And so initially we will take a and we will push it to the empty array. 16 00:00:49,730 --> 00:00:52,670 And then we'll take the next character from the left which is B. 17 00:00:52,700 --> 00:00:53,540 We'll push it. 18 00:00:53,540 --> 00:00:56,660 So two check will become this array over here. 19 00:00:56,660 --> 00:00:56,870 Right. 20 00:00:56,870 --> 00:00:58,730 So this A is over here. 21 00:00:58,730 --> 00:01:00,800 This B is over here. 22 00:01:00,800 --> 00:01:02,660 This C is over here. 23 00:01:02,660 --> 00:01:05,180 And then we take this b we push it to the array. 24 00:01:05,180 --> 00:01:07,340 And then we take this a and we push it to this array. 25 00:01:07,340 --> 00:01:10,220 So two check becomes this array over here. 26 00:01:10,220 --> 00:01:16,850 Now after this what we do is we use a join function to convert this array into a string. 27 00:01:16,850 --> 00:01:17,090 Right. 28 00:01:17,090 --> 00:01:19,880 So we convert it into a string a b c b a. 29 00:01:19,880 --> 00:01:23,210 And then we check this string and the given string. 30 00:01:23,210 --> 00:01:24,140 This is the given string. 31 00:01:24,140 --> 00:01:25,490 And we check this string. 32 00:01:25,490 --> 00:01:27,500 If they are the same we return true. 33 00:01:27,500 --> 00:01:29,960 If they are not the same, we return false. 34 00:01:29,960 --> 00:01:32,480 So this is much better than the previous solution. 35 00:01:32,480 --> 00:01:35,030 Let's look at the complexity of this solution. 36 00:01:35,030 --> 00:01:36,980 What about the time complexity? 37 00:01:37,490 --> 00:01:41,120 We can see that this has just a time complexity of O of n. 38 00:01:41,150 --> 00:01:44,630 The previous solution had a time complexity of O of n square. 39 00:01:44,630 --> 00:01:48,020 Now why is there such a drastic difference over here? 40 00:01:48,020 --> 00:01:50,150 We are pushing to the array right now. 41 00:01:50,150 --> 00:01:53,750 Pushing an element to an array is a constant time operation. 42 00:01:53,750 --> 00:01:55,940 So this is not costing us time, right? 43 00:01:55,940 --> 00:02:00,440 We are just traversing the given string once, which is an O of n operation. 44 00:02:00,440 --> 00:02:00,860 Right. 45 00:02:00,860 --> 00:02:04,730 So that's why the time complexity of this solution is O of n. 46 00:02:04,730 --> 00:02:06,800 Now what about the space complexity? 47 00:02:06,800 --> 00:02:11,750 The space complexity is also O of n because we are creating a new array. 48 00:02:11,750 --> 00:02:12,140 Right. 49 00:02:12,140 --> 00:02:15,080 And and we we have that array over here. 50 00:02:15,080 --> 00:02:15,530 Right. 51 00:02:15,530 --> 00:02:19,820 So again the space complexity over here is also O of n. 52 00:02:20,360 --> 00:02:25,760 Notice that this this new array which we created, the same array we are converting to a string. 53 00:02:25,760 --> 00:02:26,060 Right. 54 00:02:26,060 --> 00:02:30,200 So again the space we are just taking extra space to create this array. 55 00:02:30,200 --> 00:02:32,330 And then we are converting that same array into a string. 56 00:02:32,330 --> 00:02:35,480 So the space complexity of this solution is O of n.