1
00:00:02,060 --> 00:00:02,760
Hi, everyone.

2
00:00:02,780 --> 00:00:08,750
So today we are going to solve this question, valid palindrome, too, so this question is present

3
00:00:08,750 --> 00:00:09,380
only told.

4
00:00:09,470 --> 00:00:10,380
OK, so let's see.

5
00:00:11,270 --> 00:00:16,290
So this is the question really boils down to now we can read the statement here.

6
00:00:16,309 --> 00:00:22,130
So the input will be a string as and we have to delete at most.

7
00:00:22,130 --> 00:00:29,000
One character we can add makes delete one character and then we have to tell whether we can make palindrome

8
00:00:29,000 --> 00:00:29,450
or not.

9
00:00:29,930 --> 00:00:35,060
OK, so basically so the input will basically be a string.

10
00:00:36,850 --> 00:00:40,930
OK, and the output will be a boolean value, true or false?

11
00:00:41,200 --> 00:00:47,440
And our question is basically from the string, we can delete zero characters, basically do not modify

12
00:00:47,440 --> 00:00:49,720
the string or we can delete one character.

13
00:00:50,680 --> 00:00:57,460
And then we have to tell whether the leading one character can result, can make the string into a palindrome

14
00:00:57,460 --> 00:00:57,880
or not.

15
00:00:58,240 --> 00:01:00,420
OK, so you can see the example here.

16
00:01:00,670 --> 00:01:02,620
So in this case, ABC.

17
00:01:02,880 --> 00:01:06,610
OK, so ABC now, this is already a palindrome.

18
00:01:06,640 --> 00:01:08,980
OK, so we are not deleting any character.

19
00:01:09,010 --> 00:01:12,460
So basically we are deleting zero characters and the output is true.

20
00:01:12,640 --> 00:01:13,970
OK, so this is a palindrome.

21
00:01:14,350 --> 00:01:16,660
Now see this example, ABC.

22
00:01:16,840 --> 00:01:19,780
OK, so we have ABC now.

23
00:01:19,780 --> 00:01:25,780
Obviously this is not a palindrome, but if it will delete the character, see if we will to see, then

24
00:01:25,780 --> 00:01:27,220
it will become ABC.

25
00:01:27,460 --> 00:01:29,270
And this is a palindrome.

26
00:01:29,650 --> 00:01:34,460
So basically we are deleting one character and we are getting a palindrome.

27
00:01:34,480 --> 00:01:35,980
So in this case, I will return.

28
00:01:35,980 --> 00:01:36,280
True.

29
00:01:36,880 --> 00:01:37,340
OK.

30
00:01:37,510 --> 00:01:42,180
So at Max you can see here at Max we can delete zero one characters.

31
00:01:42,220 --> 00:01:45,280
OK, so at most we have to delete one character.

32
00:01:46,230 --> 00:01:50,880
OK, so in this case, we are not building any character, and in this case we are deleting one character

33
00:01:51,120 --> 00:01:53,970
to obtain the palindrome so the output will be a draw.

34
00:01:54,720 --> 00:01:59,250
OK, now there can be many examples like, for example, ABC.

35
00:02:00,000 --> 00:02:04,980
OK, so if you will delete zero characters, obviously this is not a palindrome.

36
00:02:05,130 --> 00:02:06,910
If you will delete one character.

37
00:02:07,140 --> 00:02:09,690
So let's suppose you can delete it then.

38
00:02:09,690 --> 00:02:11,009
Also, it is not a palindrome.

39
00:02:11,190 --> 00:02:13,860
If you will see then also it is not a palindrome.

40
00:02:13,880 --> 00:02:15,870
You delete be then also it is not a palindrome.

41
00:02:16,140 --> 00:02:22,770
So basically the output for ABC listing will be false because deleting zero or one character does not

42
00:02:22,770 --> 00:02:24,150
result in a palindrome.

43
00:02:24,660 --> 00:02:27,050
OK, now let's take some one example.

44
00:02:27,060 --> 00:02:29,820
For example, I have this string Abebe.

45
00:02:30,970 --> 00:02:33,330
OK, so this is my input now.

46
00:02:34,690 --> 00:02:40,430
I can delete correctly, so it will become a baby, so is it a palindrome?

47
00:02:40,450 --> 00:02:40,730
No.

48
00:02:41,230 --> 00:02:43,180
So here I deleted one character.

49
00:02:44,020 --> 00:02:47,320
Now we can also delete this character, for example.

50
00:02:47,500 --> 00:02:49,510
So it will become a verb then.

51
00:02:49,510 --> 00:02:50,820
Also, it is not a palindrome.

52
00:02:51,160 --> 00:02:55,080
If so, basically they can be like many cases of deleting one character.

53
00:02:55,090 --> 00:02:59,180
But finally, all these are not palindrome.

54
00:02:59,200 --> 00:03:01,120
So in this case, our output will be false.

55
00:03:01,180 --> 00:03:08,260
OK, so for input, Abebe, our output will be false because deleting one character cannot make the

56
00:03:08,260 --> 00:03:09,690
string into a palindrome.

57
00:03:10,510 --> 00:03:10,790
OK.

58
00:03:11,710 --> 00:03:14,840
Now let us consider this example, Abebe.

59
00:03:15,520 --> 00:03:19,770
OK, now if I delete, if I'm deleting led to this character.

60
00:03:20,020 --> 00:03:21,340
So it will become baby.

61
00:03:22,150 --> 00:03:23,670
Now this is a palindrome.

62
00:03:24,100 --> 00:03:27,700
So the output for the string ab is true.

63
00:03:27,940 --> 00:03:31,060
OK, because we can delete one character to get a palindrome.

64
00:03:31,420 --> 00:03:35,230
In this case you can also delete characters like this one.

65
00:03:35,260 --> 00:03:39,220
OK, then it will become a B.A. and this is also a palindrome.

66
00:03:40,720 --> 00:03:43,860
OK, let's take one more example.

67
00:03:47,040 --> 00:03:57,770
So let's say you have the string A, B, B, C, D, and B, OK, so in this case, if I had believed

68
00:03:57,780 --> 00:03:58,890
this character C.

69
00:03:59,830 --> 00:04:06,520
Then what will happen, so it will become A, B, the the B, so basically it will become a palindrome.

70
00:04:06,880 --> 00:04:10,270
OK, so the output for this string will be through.

71
00:04:12,450 --> 00:04:14,680
OK, now let's come to the question.

72
00:04:14,700 --> 00:04:16,350
So how are we going to solve this problem?

73
00:04:16,930 --> 00:04:20,130
OK, so how to solve this problem?

74
00:04:21,290 --> 00:04:23,750
So basically, this is a very simple problem.

75
00:04:23,780 --> 00:04:28,130
It is just a modification of the like checking palindrome problem.

76
00:04:28,160 --> 00:04:32,570
OK, so it is just the modification of a palindrome problem.

77
00:04:32,810 --> 00:04:35,020
Now let's see how we can solve this problem.

78
00:04:35,390 --> 00:04:38,420
So basically, let's take an example.

79
00:04:38,450 --> 00:04:39,260
So what we will do.

80
00:04:41,160 --> 00:04:50,940
OK, so let's take an example, let's take a small example first so I have this string ABC and let's

81
00:04:50,940 --> 00:04:55,680
say we have B and E, so this is already a palindrome.

82
00:04:56,220 --> 00:05:02,430
OK, so I will keep two pointer start pointer and pointer.

83
00:05:02,610 --> 00:05:04,640
OK, so start and they the article.

84
00:05:05,280 --> 00:05:08,460
So move ahead, start will come here and will come here.

85
00:05:08,790 --> 00:05:10,410
So startlingly equal.

86
00:05:10,440 --> 00:05:13,710
Movahed So this is start and this is and start and end.

87
00:05:13,710 --> 00:05:19,050
They both are equal so move ahead then finally start will become good and end and we can say this is

88
00:05:19,050 --> 00:05:20,100
already a palindrome.

89
00:05:20,290 --> 00:05:22,290
OK, so this is already a palindrome.

90
00:05:22,290 --> 00:05:23,100
So we will return.

91
00:05:23,100 --> 00:05:23,380
True.

92
00:05:24,240 --> 00:05:28,220
Now let's see a case where I have to delete one character to obtain the palindrome.

93
00:05:29,100 --> 00:05:31,260
So suppose I have this problem.

94
00:05:31,260 --> 00:05:32,130
A baby.

95
00:05:34,070 --> 00:05:38,660
OK, so this is my starting point, this is my end point.

96
00:05:39,790 --> 00:05:42,250
Now, starting, they are not equal.

97
00:05:42,280 --> 00:05:45,040
OK, so A and B, they are not equal.

98
00:05:45,050 --> 00:05:48,670
So I have two cases, rather two cases.

99
00:05:49,000 --> 00:05:53,200
Either I can delete A or I can be OK.

100
00:05:53,320 --> 00:05:55,090
I can delete only one character.

101
00:05:55,120 --> 00:05:59,980
OK, so either I can delete it or I can delete B academics.

102
00:05:59,980 --> 00:06:04,520
I can delete only one character so I can delete more than one characters.

103
00:06:04,540 --> 00:06:07,070
So let's suppose I am deleting it.

104
00:06:07,360 --> 00:06:09,220
Then the string will become baby.

105
00:06:09,580 --> 00:06:12,850
And if I were delete B then it will become a B.

106
00:06:13,430 --> 00:06:16,380
OK, now I will check this string for the palindrome.

107
00:06:16,570 --> 00:06:17,920
So this thing is palindrome.

108
00:06:18,220 --> 00:06:19,810
So basically the output will be true.

109
00:06:20,110 --> 00:06:22,650
So this jingled also coming out of a palindrome.

110
00:06:22,660 --> 00:06:23,970
So the output is true.

111
00:06:24,380 --> 00:06:30,100
OK, so in this case for the string ab what I will do, my output will be a true.

112
00:06:32,080 --> 00:06:40,940
OK, now suppose the string was, let's say a, B, A and let's say the OK, so in this case again.

113
00:06:40,960 --> 00:06:42,940
So this is my start pointer.

114
00:06:43,600 --> 00:06:45,100
This is my end pointer.

115
00:06:45,430 --> 00:06:48,070
So start and they are not equal.

116
00:06:48,220 --> 00:06:49,480
So I have two cases.

117
00:06:49,480 --> 00:06:52,150
Either I can delete it or I can delete the.

118
00:06:52,480 --> 00:06:59,700
So if I am deleting a I am deleting it then it will become B ID or I can delete these.

119
00:06:59,710 --> 00:07:03,530
So I am deleting the then the string will become a, b, a..

120
00:07:04,600 --> 00:07:11,620
OK, so this is not a palindrome, so it is false and this string is a palindrome.

121
00:07:11,660 --> 00:07:12,790
That output is true.

122
00:07:13,090 --> 00:07:18,760
OK, so if I will delete the character D then the string will become palindrome.

123
00:07:18,770 --> 00:07:20,020
So what I will do.

124
00:07:20,020 --> 00:07:21,960
So my output will be true basically.

125
00:07:22,000 --> 00:07:25,740
OK, so I will return true for the string early.

126
00:07:25,780 --> 00:07:32,350
OK, so for the string ability, if I read the character D then the output is basically a palindrome.

127
00:07:33,130 --> 00:07:35,530
OK, so our approach will be very simple.

128
00:07:35,860 --> 00:07:36,270
So what.

129
00:07:36,520 --> 00:07:37,960
So what we are going to do here is.

130
00:07:40,750 --> 00:07:48,460
So suppose we have a very long string, let's say a B and finally, let's little Dabi and then we have

131
00:07:48,460 --> 00:07:56,980
some characters and then again, we have, let's say, a day and let's see, OK, and these are.

132
00:07:58,240 --> 00:08:00,130
So this is a very big string.

133
00:08:00,190 --> 00:08:02,120
OK, so what will be our approach?

134
00:08:02,140 --> 00:08:04,070
So our approach is going to be very simple.

135
00:08:04,090 --> 00:08:05,180
I will keep 2.0.

136
00:08:05,560 --> 00:08:06,950
So this is a start point.

137
00:08:08,050 --> 00:08:09,280
This is an appointed.

138
00:08:09,910 --> 00:08:11,640
So start and end the article.

139
00:08:11,650 --> 00:08:12,460
So move ahead.

140
00:08:13,710 --> 00:08:18,780
Start will come here and we'll come here, start and end the article to move ahead.

141
00:08:19,770 --> 00:08:23,730
So this is my start and this is my end.

142
00:08:24,250 --> 00:08:26,700
OK, so now here the start and end.

143
00:08:26,730 --> 00:08:27,450
They are different.

144
00:08:27,530 --> 00:08:30,520
OK, so B and C, they are different.

145
00:08:30,810 --> 00:08:33,530
So whenever we will encounter this case, what will happen?

146
00:08:33,690 --> 00:08:34,890
We have two situations.

147
00:08:34,890 --> 00:08:39,510
We have two cases I can relate B or I can see.

148
00:08:40,200 --> 00:08:47,520
So if I am deleting B, if I delete B, then I am writing from here, then my string will be this one.

149
00:08:47,790 --> 00:08:48,480
OK, so.

150
00:08:49,720 --> 00:08:57,820
I have to check this string, so if this string is a palindrome, then I will return to.

151
00:09:01,110 --> 00:09:06,990
Now, the next case can be, I am deleting the correct policy, so if I were the correct WTC, then

152
00:09:06,990 --> 00:09:09,570
my string will be this to this.

153
00:09:10,080 --> 00:09:12,360
OK, so basically my string will be.

154
00:09:13,390 --> 00:09:17,200
So starting from B and it will add and da da da.

155
00:09:17,260 --> 00:09:21,190
OK, so basically here before the character, see so what I can do.

156
00:09:21,490 --> 00:09:28,510
So if I am removing basically B start, so if I'm removing start, then I have to check the palindrome

157
00:09:28,510 --> 00:09:31,210
from start plus one to end.

158
00:09:31,730 --> 00:09:38,120
OK, so you can see and it's pointing towards the C so the first cases start to start.

159
00:09:38,140 --> 00:09:44,770
So I have to check the string from start to end and if I'm deleting the end, so I am deleting and then

160
00:09:44,770 --> 00:09:47,020
I have to check the string from start plus one.

161
00:09:47,980 --> 00:09:50,590
So from start to end of minus one.

162
00:09:52,090 --> 00:09:58,960
OK, so I have two cases, first cases, check the string from start plus one to end.

163
00:10:00,220 --> 00:10:03,470
Now, the second case is so here I start.

164
00:10:03,490 --> 00:10:10,970
OK, so I have deleted start and the second cases start to and minus one.

165
00:10:10,990 --> 00:10:17,110
So here I am deleting and OK, so if either of them returns.

166
00:10:17,110 --> 00:10:17,380
True.

167
00:10:18,390 --> 00:10:25,920
If one of them returns true, then my output will be true, OK, if either dissident, true or dissident

168
00:10:25,920 --> 00:10:30,930
true, my output will become true, either one of them should return true if both of them return false.

169
00:10:31,260 --> 00:10:37,710
So if this is returning false and this is also returning false, then my output will be false.

170
00:10:37,740 --> 00:10:39,390
Otherwise, the output will be true.

171
00:10:40,130 --> 00:10:42,430
OK, so I hope you understood the question.

172
00:10:42,450 --> 00:10:44,940
Now let us write the code, ok.

173
00:10:48,290 --> 00:10:56,630
So let's then let's rename it to the name of this thing is a OK, so first of all, we are just writing

174
00:10:56,630 --> 00:10:58,070
the simple palindrome function.

175
00:10:58,100 --> 00:10:59,270
OK, so.

176
00:11:01,060 --> 00:11:02,260
The start will be zero.

177
00:11:04,090 --> 00:11:07,720
What will be and so it will be basically adult size, minus one.

178
00:11:10,480 --> 00:11:16,160
OK, and no simple condition will start is less than articles to end.

179
00:11:16,780 --> 00:11:19,970
So what I have to do so first of all, let's check.

180
00:11:20,050 --> 00:11:20,800
So if.

181
00:11:23,200 --> 00:11:25,960
If this start is not close to end.

182
00:11:28,690 --> 00:11:33,830
So I start to question what I have to do, so I have to do some work I have to handle to get it.

183
00:11:33,880 --> 00:11:35,970
OK, so two cases will be there.

184
00:11:37,190 --> 00:11:41,450
Otherwise, I'm going to do start plus, plus and minus minus.

185
00:11:41,910 --> 00:11:46,020
OK, and finally, if we are not building any character.

186
00:11:46,040 --> 00:11:48,170
OK, so this thing is basically a palindrome.

187
00:11:48,170 --> 00:11:49,130
String is.

188
00:11:50,100 --> 00:11:51,210
Already palindrome.

189
00:11:56,370 --> 00:11:59,790
So everything is already a palindrome then we can return to.

190
00:12:01,270 --> 00:12:11,830
OK, now I have to handle two cases, so either delayed start so we can start, then I have to check

191
00:12:11,830 --> 00:12:12,160
for.

192
00:12:13,210 --> 00:12:14,740
I have to check for a string.

193
00:12:16,500 --> 00:12:19,860
I have to check for string starting from start plus one.

194
00:12:21,210 --> 00:12:29,820
The end and the second cases delayed the end, so delayed and then I have to check for the string.

195
00:12:32,950 --> 00:12:35,860
So I have to check for the string starting from start.

196
00:12:37,220 --> 00:12:38,480
Two and a minus one.

197
00:12:39,260 --> 00:12:44,090
OK, so these are the two cases that we need to handle here, so let's try to function first.

198
00:12:45,820 --> 00:12:48,550
So I am writing a function to bool.

199
00:12:49,530 --> 00:12:56,250
Check now this check function is taking a string as input string, and it will take a start and end.

200
00:12:56,540 --> 00:13:00,510
OK, so it is taking start and end.

201
00:13:02,320 --> 00:13:06,790
Now, I will write this simple code, so we'll start this list in articles to end.

202
00:13:08,200 --> 00:13:14,410
Would I have to do so if I start is not going to offend?

203
00:13:16,480 --> 00:13:18,100
Then I congratulated Penfold's.

204
00:13:19,920 --> 00:13:26,520
OK, otherwise, I am going to start plus, plus and minus minus, and here I am returning to.

205
00:13:32,430 --> 00:13:33,300
So basically.

206
00:13:35,160 --> 00:13:39,960
So basically what this function will do, so it will take a string as input, it will take the starting

207
00:13:39,960 --> 00:13:41,580
point, it will take the ending point.

208
00:13:41,640 --> 00:13:44,130
OK, so suppose I have a very long string.

209
00:13:44,670 --> 00:13:50,850
So I have given this starting point and I have given the ending point so dysfunctional this function

210
00:13:50,850 --> 00:13:52,500
will check this part of the string.

211
00:13:53,440 --> 00:13:56,070
It will only this part of the string for palindrome.

212
00:13:56,100 --> 00:14:02,340
OK, so if it is not a palindrome, if this part is not a palindrome, it will return false if this

213
00:14:02,340 --> 00:14:03,940
part is a total return.

214
00:14:03,960 --> 00:14:04,220
True.

215
00:14:04,410 --> 00:14:08,310
OK, so this check function, it will not check the complete string.

216
00:14:08,310 --> 00:14:10,750
It will only check a part of the string, OK.

217
00:14:11,160 --> 00:14:12,930
It will only check a part of the string.

218
00:14:15,380 --> 00:14:21,410
So what I have to do, so I have two cases, two first cases I'm calling the function check.

219
00:14:22,900 --> 00:14:29,050
String is a and let's say I am deleting as so I will pass Astarte plus one to end.

220
00:14:29,380 --> 00:14:34,180
Now the second case is let's call the check function.

221
00:14:34,450 --> 00:14:36,250
String is a now.

222
00:14:36,610 --> 00:14:38,140
I will delete the end.

223
00:14:38,170 --> 00:14:40,810
So I'm deleting and so I will pass and minus one.

224
00:14:41,900 --> 00:14:49,790
So if either of them, either this one or I did this one, if either of them returns true, I will return

225
00:14:49,790 --> 00:14:50,060
to.

226
00:14:52,420 --> 00:14:53,440
In the aspart.

227
00:14:55,060 --> 00:14:56,200
I will return false.

228
00:14:58,380 --> 00:15:00,220
So basically, what is the meaning here?

229
00:15:00,750 --> 00:15:04,590
So when everything falls, that means after deleting one character.

230
00:15:07,160 --> 00:15:10,590
After deleting one character, we are not able to make the string palindrome.

231
00:15:10,610 --> 00:15:14,990
OK, so we are unable to obtain.

232
00:15:16,460 --> 00:15:18,140
Apelin lobstering, OK?

233
00:15:19,830 --> 00:15:24,960
So we after building one character, we are unable to obtain a palindrome string, then I can return

234
00:15:24,960 --> 00:15:25,350
false.

235
00:15:25,500 --> 00:15:29,400
OK, so this is very simple code and all this stuff called.

236
00:15:35,340 --> 00:15:36,270
Knowledge summit.

237
00:15:40,630 --> 00:15:45,490
OK, so our goal is working fine now let us discuss the time and the space complexity.

238
00:15:46,240 --> 00:15:52,990
So basically the time complexities are there often and the space complexities big of one.

239
00:15:53,110 --> 00:15:56,150
OK, so this is the time and the space complexity for this problem.

240
00:15:56,740 --> 00:16:02,320
So if you have any doubt in this question, you can ask me, OK, so this question was very simple.

241
00:16:02,330 --> 00:16:06,040
We are just like it is just a modification of the palindrome problem.

242
00:16:06,050 --> 00:16:09,190
OK, simple modification of Ballenden problem.

243
00:16:10,110 --> 00:16:14,640
OK, so if you have any doubt, please ask me, OK, thank you.

