1
00:00:00,390 --> 00:00:02,250
Hello, everyone, and welcome back.

2
00:00:02,340 --> 00:00:07,950
Hopefully you got a chance to try and come up with a solution and code it yourself for our almost palindrome

3
00:00:07,950 --> 00:00:08,700
problem.

4
00:00:09,210 --> 00:00:12,060
In this lesson, I'm going to show you how I would do it.

5
00:00:12,090 --> 00:00:20,010
The first thing that I would do is look at the question and realize that the palindrome definition portion

6
00:00:20,010 --> 00:00:26,520
of the question, which is where we identify if some string or substring in the problem is a palindrome,

7
00:00:26,520 --> 00:00:29,190
is only a sub problem.

8
00:00:29,190 --> 00:00:34,440
So this goes back to what I was mentioning earlier about how palindromes appear in string questions,

9
00:00:34,440 --> 00:00:38,490
but mainly as sub problems, not as the main problem itself.

10
00:00:38,760 --> 00:00:45,120
So, yes, our question is similar to us trying to figure out if we have a valid palindrome or not.

11
00:00:45,120 --> 00:00:47,340
But it's not the whole picture.

12
00:00:47,610 --> 00:00:52,040
The key thing that we are trying to figure out is looking at the string.

13
00:00:52,050 --> 00:00:59,370
Is there a conflict in such a way between two characters where by removing one of the characters, we

14
00:00:59,370 --> 00:01:01,230
end up with a palindrome?

15
00:01:01,230 --> 00:01:08,370
That's actually the key thing we're trying to solve is figuring out which characters in this string

16
00:01:08,370 --> 00:01:14,100
have the conflict and then figuring out how to generate the new versions of the strings.

17
00:01:14,100 --> 00:01:19,530
With those characters removed, we then need to check if either string is a palindrome.

18
00:01:19,530 --> 00:01:26,040
So here we can see that once we've generated our two strings, we definitely need to leverage one of

19
00:01:26,040 --> 00:01:30,270
those three solutions we have for figuring out if a string is a palindrome.

20
00:01:30,270 --> 00:01:35,520
Because we're going to have to use one of those three solutions on the two generated strings.

21
00:01:35,790 --> 00:01:42,750
The other thing that we notice is that if this string is by default a palindrome, meaning that we don't

22
00:01:42,750 --> 00:01:48,840
have to remove any character, we have to have some way of checking to see if that's the case.

23
00:01:48,840 --> 00:01:51,210
So that gives us a big hint.

24
00:01:51,720 --> 00:01:58,680
Knowing that this string can be a palindrome means that we can probably utilize one of those three solutions

25
00:01:58,680 --> 00:02:02,220
as a starting point to figure out an optimal solution.

26
00:02:02,490 --> 00:02:09,210
So with that in mind, let's use process of elimination to figure out which of those three is most ideal

27
00:02:09,300 --> 00:02:12,660
to start applying to this string question.

28
00:02:13,140 --> 00:02:19,470
So the first thing we notice is that if we were to use the reverse string method, what we do is we

29
00:02:19,470 --> 00:02:25,350
generate a reverse of this string, and what we do is we then compare the values.

30
00:02:25,350 --> 00:02:30,600
So here it would be a, B, D, C, C, be a.

31
00:02:31,080 --> 00:02:37,140
Our solution then uses an equality check to see if these strings are equal and we can see that they

32
00:02:37,140 --> 00:02:38,160
already are not.

33
00:02:38,160 --> 00:02:43,290
We know that the D and the C will conflict, but our solution because it's in a quality check, doesn't

34
00:02:43,290 --> 00:02:44,880
actually give us that information.

35
00:02:44,880 --> 00:02:50,700
We can visually see because we know this string is not a palindrome, but we can already tell that this

36
00:02:50,700 --> 00:02:57,090
is not going to be the right solution to work with because it gives us no information about where the

37
00:02:57,090 --> 00:02:59,250
actual conflicting characters are.

38
00:02:59,250 --> 00:03:05,190
And we know that that's a key piece of information we need because we need to generate strings once

39
00:03:05,190 --> 00:03:07,320
we know the conflicting characters.

40
00:03:07,320 --> 00:03:13,860
So from here, then let's actually explore the other two options, because we've eliminated this reversal

41
00:03:13,860 --> 00:03:15,330
comparison solution.

42
00:03:15,660 --> 00:03:21,390
So the other two options we have is to generate left and right pointers, either from the center of

43
00:03:21,390 --> 00:03:26,790
the string or from the outside of the string, if we think about that.

44
00:03:27,340 --> 00:03:33,550
We know that the center generation is a little bit more complicated because we do have to account for

45
00:03:33,550 --> 00:03:35,770
whether or not the string is on or even.

46
00:03:35,770 --> 00:03:41,160
And if we think about it in those terms, that solution is ever so slightly more complicated.

47
00:03:41,170 --> 00:03:44,440
It doesn't actually affect the space and time complexity.

48
00:03:44,530 --> 00:03:48,400
But here, let's just use the left and right pointers from the outside.

49
00:03:48,400 --> 00:03:53,530
For simplicity's sake, we can easily go with the other one, but because this one is a little simpler

50
00:03:53,530 --> 00:03:59,860
to implement, it gives us less moving pieces to work around with because we have to still transform

51
00:03:59,860 --> 00:04:04,240
the solution a little bit in order for it to work to this new current problem.

52
00:04:04,600 --> 00:04:11,140
So let's say we go with that solution where we initialize a left pointer and a right pointer on the

53
00:04:11,140 --> 00:04:13,210
outside edges of the string.

54
00:04:13,510 --> 00:04:19,690
We compare these two values the A and the A, and we see that they're equal so that we move the pointers

55
00:04:19,690 --> 00:04:20,709
inwards here.

56
00:04:21,399 --> 00:04:24,580
And when we compare these new characters, we see they're still equal.

57
00:04:24,580 --> 00:04:25,120
They're both.

58
00:04:25,150 --> 00:04:32,680
B So we move the pointers again and now we see that we have a conflict, the C and the D conflict.

59
00:04:32,800 --> 00:04:39,160
So what we then do is we want to generate new strings, removing either of these characters.

60
00:04:39,430 --> 00:04:47,050
So here we're going to generate a, b, c, c, b, a from removing this D right here.

61
00:04:47,410 --> 00:04:54,010
And then we're going to generate our other string by removing this C, so we end up with a, B, C,

62
00:04:54,040 --> 00:05:01,300
D, b, a now that we have our two strings, we need to figure out if they are palindromes.

63
00:05:01,300 --> 00:05:07,420
So how we can do this is remember with our original string, we've already checked these characters,

64
00:05:07,420 --> 00:05:13,300
so we don't need to check these characters anymore because they are not the ones that changed, the

65
00:05:13,300 --> 00:05:16,360
ones that changed our in the position of left and right.

66
00:05:16,360 --> 00:05:22,170
So at the indices that the left and right pointers in our original string is pointing at.

67
00:05:22,180 --> 00:05:29,920
So we can just continue from there and just do our checks from here while continuing to move inwards.

68
00:05:29,980 --> 00:05:35,080
Now, I know that here we only have two characters left, but if there were more, you would just check

69
00:05:35,080 --> 00:05:38,020
these characters, keep going in, check the characters, keep going in.

70
00:05:38,020 --> 00:05:44,530
And from there you can just say if whatever is remaining inside of this string, if they match the palindrome

71
00:05:44,530 --> 00:05:47,470
pattern matching, then we know that this is a palindrome.

72
00:05:47,590 --> 00:05:50,100
If they don't, then we know it's not a palindrome.

73
00:05:50,110 --> 00:05:52,410
There's no more characters we have left to remove.

74
00:05:52,420 --> 00:05:55,690
So from here we see that this is indeed matching.

75
00:05:55,690 --> 00:05:57,840
So this string is a palindrome.

76
00:05:57,850 --> 00:05:59,170
This one doesn't match.

77
00:05:59,170 --> 00:06:00,520
So it's not a palindrome.

78
00:06:00,520 --> 00:06:03,700
But because this one is, we have our answer.

79
00:06:03,700 --> 00:06:09,670
So we know that this is indeed an almost palindrome, because one of the strings from the character

80
00:06:09,670 --> 00:06:11,800
we removed became a palindrome.

81
00:06:12,800 --> 00:06:15,830
So I want to challenge you to code out this solution.

82
00:06:16,250 --> 00:06:17,840
I will give you a hint.

83
00:06:17,930 --> 00:06:26,540
The key is going to be around passing this original string into some kind of function that will then

84
00:06:26,540 --> 00:06:33,380
check whether or not we have a palindrome by passing not only the string, but also the current left

85
00:06:33,380 --> 00:06:34,490
and right pointers.

86
00:06:34,490 --> 00:06:41,450
And one of these pointers needs to be the one that is technically removing the character by shifting

87
00:06:41,450 --> 00:06:42,200
inwards.

88
00:06:42,620 --> 00:06:46,160
Hopefully that's enough of a hint, and I want to challenge you to try it out.

89
00:06:46,160 --> 00:06:49,400
In the next lesson, I'm going to show you how we're going to code the solution.