1 00:00:01,500 --> 00:00:02,200 Hi, everyone. 2 00:00:02,220 --> 00:00:05,700 So today we are going to solve this problem, valid palindrome. 3 00:00:05,730 --> 00:00:11,020 OK, so given a string, we have to check whether the string is a palindrome or not. 4 00:00:11,040 --> 00:00:15,930 For example, this string A.B.C., so this is not a palindrome. 5 00:00:16,230 --> 00:00:18,030 So what is the meaning of palindrome? 6 00:00:18,030 --> 00:00:23,760 So palindrome means, if you will, read from left to right or if you read from right to left, then 7 00:00:23,760 --> 00:00:24,930 they both will be equal. 8 00:00:25,870 --> 00:00:33,030 OK, so in this case, if I will read from left to right, this is ABC and if I will read from right 9 00:00:33,030 --> 00:00:34,800 to left, then this is S.B. 10 00:00:35,220 --> 00:00:37,050 And obviously these two are not equal. 11 00:00:37,560 --> 00:00:39,360 OK, so our output should be false. 12 00:00:40,020 --> 00:00:45,990 OK, so the return type of our function will be a boolean value and the input will be a string. 13 00:00:47,250 --> 00:00:53,400 Let's take one more example, so if I have this string A, B, if you will read from left to right, 14 00:00:53,400 --> 00:01:00,060 then obviously this is B and if you will read from right to left, then also it is A B and these both 15 00:01:00,060 --> 00:01:00,520 are equal. 16 00:01:00,540 --> 00:01:01,380 So I will return. 17 00:01:01,380 --> 00:01:01,630 True. 18 00:01:02,710 --> 00:01:04,250 OK, so this is the significance. 19 00:01:04,260 --> 00:01:05,940 This is the meaning of a palindrome. 20 00:01:06,120 --> 00:01:09,690 OK, so how to check with a given string is a palindrome of note. 21 00:01:09,870 --> 00:01:10,970 So this is very simple. 22 00:01:11,010 --> 00:01:14,280 For example, let's say this is let's take a string. 23 00:01:14,280 --> 00:01:17,040 So A, B, C, C and let's say the. 24 00:01:18,590 --> 00:01:20,790 OK, so this is basically a palindrome. 25 00:01:20,810 --> 00:01:22,310 Now let's see how we will check it. 26 00:01:22,580 --> 00:01:29,550 So take two point us start pointer and pointer, OK, start and end vertical. 27 00:01:29,570 --> 00:01:31,040 So and they both are equal. 28 00:01:31,050 --> 00:01:31,560 Move ahead. 29 00:01:31,910 --> 00:01:33,230 So this is a start. 30 00:01:33,410 --> 00:01:33,880 This is. 31 00:01:33,890 --> 00:01:39,770 And so basically what I am doing here, I am doing a start plus and I'm going and minus minus. 32 00:01:40,050 --> 00:01:43,840 OK, now compare me with B so be NBA to move ahead. 33 00:01:43,850 --> 00:01:47,330 So we'll start plus plus and minus minus. 34 00:01:47,720 --> 00:01:49,610 Now see an equal move ahead. 35 00:01:49,790 --> 00:01:52,980 So we'll start plus plus and minus minus. 36 00:01:53,240 --> 00:01:58,240 So compare the with B so these equal to the then move ahead. 37 00:01:58,250 --> 00:02:04,120 So I will start plus plus and minus minus two start will come here and will come here. 38 00:02:04,400 --> 00:02:08,889 So this will become start basically and and will come here. 39 00:02:09,350 --> 00:02:11,020 So when we will stop. 40 00:02:11,030 --> 00:02:15,700 So when the start is less than end or basically when the end. 41 00:02:16,310 --> 00:02:16,760 OK. 42 00:02:16,790 --> 00:02:19,740 So basically when the start becomes good then. 43 00:02:19,760 --> 00:02:21,740 And so this is the condition. 44 00:02:21,800 --> 00:02:27,980 OK, so when the start becomes good then end, then I can say that my string is basically a palindrome. 45 00:02:29,890 --> 00:02:35,380 OK, so I'm just quickly writing the code and then we will see the little problem. 46 00:02:35,410 --> 00:02:40,030 OK, so the problem is a little bit of advanced version of this problem. 47 00:02:40,320 --> 00:02:45,540 OK, so for simply checking a palindrome, how we can write the code. 48 00:02:45,550 --> 00:02:46,830 So I will take two pointer. 49 00:02:47,650 --> 00:02:54,850 So the first pointer will be at the start and the end point will be and minus one basically at the end 50 00:02:54,850 --> 00:02:55,240 point. 51 00:02:55,510 --> 00:02:58,260 And then what is the conditions of condition is very simple. 52 00:02:58,570 --> 00:03:03,960 We'll start this less than than to end what I have to do, I have to compare both start and end. 53 00:03:04,150 --> 00:03:07,170 So let's say many of the error is a. 54 00:03:07,210 --> 00:03:16,450 So if a start is not close to AOF and then you can simply return false, you can simply return false. 55 00:03:16,930 --> 00:03:19,730 Otherwise what you can do, we will lose start plus. 56 00:03:19,750 --> 00:03:21,380 Plus we will do and minus minus. 57 00:03:21,790 --> 00:03:24,730 And finally we will return to. 58 00:03:26,270 --> 00:03:32,330 OK, so this is when the palindrome vendor given string is very simple string. 59 00:03:32,540 --> 00:03:37,340 OK, so the lead problem, the literal problem is very different. 60 00:03:37,850 --> 00:03:38,950 It is not very different. 61 00:03:38,960 --> 00:03:40,340 It is slightly different. 62 00:03:40,370 --> 00:03:43,800 OK, so this is our little problem. 63 00:03:44,060 --> 00:03:50,420 So as you can see, so this problem is a little bit different, although the concept will remain the 64 00:03:50,420 --> 00:03:50,690 same. 65 00:03:50,930 --> 00:03:52,310 So how we will check. 66 00:03:52,580 --> 00:03:56,380 So for example, I will compare capitally and small. 67 00:03:56,690 --> 00:03:58,850 So in this case they are assuming both are. 68 00:03:59,210 --> 00:04:01,100 OK, so capital and small. 69 00:04:01,100 --> 00:04:01,790 They both are slim. 70 00:04:02,090 --> 00:04:05,330 Then if I will do so, this is my start, then this is my end. 71 00:04:05,510 --> 00:04:08,400 So if I will do start placeless, I will reach here. 72 00:04:08,420 --> 00:04:09,770 Basically this is a space. 73 00:04:10,500 --> 00:04:14,320 OK, so this problem says if it is a space, then move ahead. 74 00:04:14,330 --> 00:04:15,430 So I will reach M. 75 00:04:16,529 --> 00:04:20,410 And similarly, I am here, so mnm motoric, well, I will move ahead. 76 00:04:20,880 --> 00:04:27,240 So basically this problem is you will be given space's, you will be given Goma's, you will be given 77 00:04:27,240 --> 00:04:30,870 capital and small letters and you will be given semicolon. 78 00:04:30,890 --> 00:04:33,020 You will be given special characters and so on. 79 00:04:33,570 --> 00:04:36,030 So basically you will be given a complex string. 80 00:04:36,270 --> 00:04:39,630 But what you will compare, you will only compare numbers. 81 00:04:41,040 --> 00:04:47,940 And you will compare Alphabet's and you will skip all these. 82 00:04:47,970 --> 00:04:54,210 OK, so we will skip spaces, we will speak, we will skip special characters, for example, Daulaire 83 00:04:54,210 --> 00:04:57,480 or for example and or and so on. 84 00:04:57,890 --> 00:05:01,260 OK, so we have to compare only numbers and alphabets. 85 00:05:02,680 --> 00:05:07,700 OK, and in the alphabet, both upper and lower case, they are equal. 86 00:05:07,720 --> 00:05:13,780 OK, so they are not different, but apparently what cases they are saying, OK, so the approach is 87 00:05:13,780 --> 00:05:14,680 exactly the same. 88 00:05:14,950 --> 00:05:22,790 Take two pointers at the first start point and then the pointer moves start and end and compare. 89 00:05:23,620 --> 00:05:29,680 OK, so if you start and end, if they are not equal, you can return false and if they are equal, 90 00:05:29,710 --> 00:05:33,160 you can to true and you have to take care of these type of cases. 91 00:05:33,190 --> 00:05:35,770 OK, we will only consider no alphabet's. 92 00:05:37,940 --> 00:05:43,280 OK, so let us read the code, so the approach is very simple, we have to take two variables. 93 00:05:43,850 --> 00:05:44,870 Start will be zero. 94 00:05:46,360 --> 00:05:50,620 And the end will be basically Astarte size minus one. 95 00:05:52,000 --> 00:05:55,930 Let's store it basically and is basically the same as Nazis'. 96 00:05:58,610 --> 00:06:01,250 Now, what will be the end so and will be N minus one. 97 00:06:02,030 --> 00:06:03,520 OK, now what we have to do. 98 00:06:03,530 --> 00:06:06,920 So we'll start this list on articles two and. 99 00:06:08,550 --> 00:06:11,430 We will do something, and at the end we will return to. 100 00:06:15,230 --> 00:06:18,170 OK, so inside this part, what we have to do. 101 00:06:20,090 --> 00:06:21,080 So first of all. 102 00:06:22,850 --> 00:06:27,010 What we have to do, we have to check whether they start and end, they are equal or not. 103 00:06:27,020 --> 00:06:28,490 So if. 104 00:06:30,830 --> 00:06:34,560 So, OK, so this is let's change the name. 105 00:06:34,580 --> 00:06:37,850 This is a basically OK, so this is a. 106 00:06:40,040 --> 00:06:43,730 So if the start is not close to end. 107 00:06:45,460 --> 00:06:46,300 I can return. 108 00:06:48,900 --> 00:06:53,520 False else, I will do start placeless and I will do and minus minus. 109 00:06:53,910 --> 00:06:57,780 OK, but this code is not enough, but I have to do so. 110 00:06:57,780 --> 00:07:02,060 The characters can be uppercase or lowercase, so there is a function to appear. 111 00:07:02,760 --> 00:07:07,430 OK, so I will use a function to appear to WOPR function. 112 00:07:07,920 --> 00:07:08,670 So to. 113 00:07:09,700 --> 00:07:11,500 A paratrooper function takes. 114 00:07:13,440 --> 00:07:16,350 A character has input and it will return the Oscar value. 115 00:07:16,440 --> 00:07:17,820 OK, so to upper. 116 00:07:21,170 --> 00:07:23,960 It will return the value of the character. 117 00:07:24,410 --> 00:07:29,150 OK, so I am using to function now, is this correct? 118 00:07:29,720 --> 00:07:31,920 So I think this is still not correct. 119 00:07:32,390 --> 00:07:40,310 So basically, I have not handled the cases when the character is basically space or basically special 120 00:07:40,310 --> 00:07:40,850 characters. 121 00:07:40,880 --> 00:07:42,350 So I have to skip all this. 122 00:07:42,720 --> 00:07:45,080 OK, so I have to skip all of them. 123 00:07:46,550 --> 00:07:52,460 So I'll start this less than what it to end what I have to do, I have to skip all those characters. 124 00:07:55,030 --> 00:07:58,570 And the character is neither Alphabeat and nor No. 125 00:08:00,110 --> 00:08:04,490 So I will give a start what I have to do, I will start placeless. 126 00:08:06,650 --> 00:08:09,110 And similarly, the same condition for the end. 127 00:08:11,970 --> 00:08:21,070 So while the end character is neither Alphabeat and not a numeric number, I will do it and minus minus. 128 00:08:21,630 --> 00:08:23,520 OK, so let me show you. 129 00:08:24,360 --> 00:08:26,310 So basically this function is called. 130 00:08:27,680 --> 00:08:34,640 So what dysfunctional dysfunction will take a character as input and it will return true if the character 131 00:08:34,640 --> 00:08:43,010 is either Alphabeat or if the character is either a no and in all other cases dysfunctional, it unfolds. 132 00:08:44,450 --> 00:08:54,260 OK, so basically if it returns false, that means I have like Space's commas, semicolons, Dolev symbol. 133 00:08:54,260 --> 00:08:58,340 Aanenson And our aim was to skip all these characters. 134 00:08:58,520 --> 00:09:04,850 OK, so if they start, if they start as all these characters, then I will do start placeless. 135 00:09:04,970 --> 00:09:11,240 And similarly if the end and also all these characters then I will do and minus minus now at this point. 136 00:09:12,450 --> 00:09:18,750 At this point, I am very sure that I have alphabet or numbers. 137 00:09:18,990 --> 00:09:20,920 OK, I have alphabet on numbers. 138 00:09:20,940 --> 00:09:25,410 I am very sure at this point then what I am doing, I am using to upper function. 139 00:09:25,590 --> 00:09:28,110 So do upper functions or to upper function. 140 00:09:28,110 --> 00:09:33,610 What it will do, it will take a character input and it will return the ascribe value. 141 00:09:34,680 --> 00:09:37,320 OK, and then we are comparing the ASCII values. 142 00:09:37,650 --> 00:09:38,730 OK, very simple. 143 00:09:38,820 --> 00:09:41,830 If the values are different, I am returning false. 144 00:09:41,940 --> 00:09:44,420 Otherwise I will lose plus plus and minus minus. 145 00:09:44,430 --> 00:09:45,660 And finally I am returning. 146 00:09:45,660 --> 00:09:45,920 True. 147 00:09:46,200 --> 00:09:50,250 So basically the time complexities win and the space complexities or even. 148 00:09:50,640 --> 00:09:54,510 OK, so this is time and this is space. 149 00:09:54,510 --> 00:09:56,180 We are not using any extra space. 150 00:09:56,190 --> 00:09:58,230 OK, so constant space and linear time. 151 00:09:59,440 --> 00:10:06,250 OK, so there are many functions, for example, to operate, there are many functions like to lower. 152 00:10:07,560 --> 00:10:09,840 We have also functions like his lower. 153 00:10:10,920 --> 00:10:12,270 Like is upper. 154 00:10:14,010 --> 00:10:14,740 And so on. 155 00:10:14,880 --> 00:10:15,310 OK. 156 00:10:15,570 --> 00:10:20,960 And like we also have functions like is Richard is Alpha, OK? 157 00:10:21,150 --> 00:10:26,340 We have functions like is digit is alpha. 158 00:10:27,380 --> 00:10:28,880 And and many more. 159 00:10:28,910 --> 00:10:35,390 OK, so we have many functions that are already implemented in C++ for our own help. 160 00:10:35,420 --> 00:10:38,890 OK, so here I'm using is Ellum OK? 161 00:10:38,930 --> 00:10:45,800 Is a lung function that will return MITRO if the given character is either Alphabeat or no, otherwise 162 00:10:45,800 --> 00:10:46,850 it will return false. 163 00:10:47,210 --> 00:10:51,560 OK, so we need this function here because you can see the example. 164 00:10:52,790 --> 00:10:54,920 I do not need to compare spaces. 165 00:10:54,950 --> 00:10:57,830 OK, I have to skip spaces, I have to skip commas. 166 00:10:57,830 --> 00:11:00,260 I have to skip this columns and so on. 167 00:11:01,250 --> 00:11:08,090 OK, so for skipping we are using is Ellem and obviously you can see so this is uppercase and this is 168 00:11:08,120 --> 00:11:08,810 lowercase. 169 00:11:09,230 --> 00:11:14,720 So for upper and lower I'm using two upper function, I'm converting the I'm converting everything to 170 00:11:14,720 --> 00:11:15,290 uppercase. 171 00:11:15,920 --> 00:11:16,310 OK. 172 00:11:17,610 --> 00:11:20,420 OK, so I think everything is fine now. 173 00:11:20,430 --> 00:11:21,960 Let us try to land our good. 174 00:11:24,760 --> 00:11:25,960 OK, now let's Sombat. 175 00:11:27,460 --> 00:11:28,910 So our goal will work fine. 176 00:11:28,930 --> 00:11:29,240 OK. 177 00:11:29,650 --> 00:11:36,940 I think we did everything correctly, so the time, complexities in the space, complexities on OK, 178 00:11:37,120 --> 00:11:42,090 so if you have any doubt in this problem, so this is valid Burrendong problem. 179 00:11:42,130 --> 00:11:44,580 So if you have any doubt in this problem, you can ask me. 180 00:11:44,590 --> 00:11:46,270 OK, thank you.