1
00:00:00,360 --> 00:00:02,010
Hello, everyone, and welcome back.

2
00:00:02,460 --> 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:11,850
problem in this lesson, I'm going to show you how I would do it.

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

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

6
00:00:26,640 --> 00:00:29,020
is only a sub problem.

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

8
00:00:34,470 --> 00:00:38,320
but mainly as sub problems, not as the main problem itself.

9
00:00:38,910 --> 00:00:44,940
So, yes, our question is similar to us trying to figure out if we have a valid palindrome or not.

10
00:00:45,240 --> 00:00:47,110
But it's not the whole picture.

11
00:00:47,730 --> 00:00:52,030
The key thing that we are trying to figure out is looking at the string.

12
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

13
00:00:59,370 --> 00:01:01,080
end up with a palindrome?

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

15
00:01:08,430 --> 00:01:15,060
have the conflict and then figuring out how to generate the new versions of the strings with those characters

16
00:01:15,060 --> 00:01:15,630
removed.

17
00:01:16,110 --> 00:01:19,400
We then need to check if either string is a palindrome.

18
00:01:19,650 --> 00:01:26,010
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:31,080
those three solutions we have for figuring out if a string is a palindrome, because we're going to

20
00:01:31,080 --> 00:01:35,320
have to use one of those three solutions on the two generated strings.

21
00:01:35,940 --> 00:01:42,780
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,780 --> 00:01:48,590
have to remove any character, we have to have some way of checking to see if that's the case.

23
00:01:49,020 --> 00:01:51,030
So that gives us a big hint.

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

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

26
00:02:02,640 --> 00:02:09,000
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,450 --> 00:02:12,500
to start applying to this string question.

28
00:02:13,260 --> 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:21,660
generate a reverse of this string.

30
00:02:22,050 --> 00:02:25,400
And what we do is we then compare the values.

31
00:02:25,440 --> 00:02:34,380
So here it would be A, B, C, C, B, A, our solution then uses and a quality check to see if these

32
00:02:34,380 --> 00:02:38,160
strings are equal and we can see that they already are not.

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

34
00:02:43,320 --> 00:02:48,210
actually give us that information we can visually see because we know the string is not a palindrome,

35
00:02:48,600 --> 00:02:54,090
but we can already tell that this is not going to be the right solution to work with because it gives

36
00:02:54,090 --> 00:02:59,160
us no information about where the actual conflicting characters are.

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

38
00:03:05,220 --> 00:03:07,090
we know the conflicting characters.

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

40
00:03:13,860 --> 00:03:15,170
comparison solution.

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

42
00:03:21,390 --> 00:03:23,830
the string or from the outside of the string.

43
00:03:24,660 --> 00:03:32,160
If we think about that, we know that the center generation is a little bit more complicated because

44
00:03:32,160 --> 00:03:35,640
we do have to account for whether or not the string is oter even.

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

46
00:03:41,190 --> 00:03:44,250
It doesn't actually affect the space and time complexity.

47
00:03:44,670 --> 00:03:49,890
But here, let's just use the left and right pointers from the outside for simplicity's sake.

48
00:03:50,100 --> 00:03:51,720
We can easily go the other one.

49
00:03:51,720 --> 00:03:56,760
But because this one's a little simpler to implement, it gives us the less moving pieces to work around

50
00:03:56,760 --> 00:04:03,120
with because we have to still transform the solution a little bit in order for it to work to this new

51
00:04:03,510 --> 00:04:04,100
problem.

52
00:04:04,710 --> 00:04:11,130
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,130 --> 00:04:13,070
outside edges of the string.

54
00:04:13,650 --> 00:04:19,680
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,740 --> 00:04:20,550
inwards here.

56
00:04:21,480 --> 00:04:25,470
And when we compare these new characters, we see they're still equal, they're both be.

57
00:04:25,800 --> 00:04:32,460
So we move the pointers again and now we see that we have a conflict, the C and the D conflict.

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

59
00:04:39,570 --> 00:04:46,890
So here we're going to generate A, B, C, C, B, A from removing this D right here.

60
00:04:47,490 --> 00:04:54,060
And then we're going to generate our other string by removing this C, so we end up with A, B, C,

61
00:04:54,060 --> 00:04:55,650
D, B, a.

62
00:04:56,680 --> 00:05:02,740
Now than we ever two strings, we need to figure out if they are palindromes, so how we can do this

63
00:05:02,740 --> 00:05:08,560
is remember, with our original string, we've already checked these characters, so we don't need to

64
00:05:08,560 --> 00:05:12,790
check these characters anymore because they are not the ones that changed.

65
00:05:13,120 --> 00:05:16,380
The ones that changed are in the position of left and right.

66
00:05:16,390 --> 00:05:23,170
So at the indices that the left and right pointers in our original string is pointing it so we can just

67
00:05:23,170 --> 00:05:29,680
continue from there and just do our checks from here while continuing to move inwards.

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

69
00:05:35,110 --> 00:05:36,850
these characters, keep going in, check.

70
00:05:36,850 --> 00:05:37,900
The characters keep going in.

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

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

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

74
00:05:50,140 --> 00:05:52,200
There's no more character we have left to remove.

75
00:05:52,600 --> 00:05:55,710
So from here, we see that this is indeed matching.

76
00:05:55,720 --> 00:05:57,650
So this string is a palindrome.

77
00:05:58,000 --> 00:05:59,200
This one doesn't match.

78
00:05:59,200 --> 00:06:00,400
So it's not a palindrome.

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

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

81
00:06:09,820 --> 00:06:11,650
removed became a palindrome.

82
00:06:12,910 --> 00:06:17,580
So I want to challenge you to coat out this solution, I will give you a hint.

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

84
00:06:26,560 --> 00:06:33,400
check whether or not we have a palindrome, bypassing not only the string, but also the current left

85
00:06:33,400 --> 00:06:34,330
and right pointers.

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

87
00:06:41,440 --> 00:06:42,030
inwards.

88
00:06:42,670 --> 00:06:44,130
Hopefully that's enough of a hint.

89
00:06:44,440 --> 00:06:47,110
And I want to challenge you to try it out in the next lesson.

90
00:06:47,110 --> 00:06:49,240
I'm going to show you how we're going to code the solution.