1
00:00:00,060 --> 00:00:01,890
Hello everyone and welcome back.

2
00:00:02,440 --> 00:00:03,970
Hopefully you got a chance to try and

3
00:00:03,980 --> 00:00:08,390
come up with a solution and code it
yourself for our almost palindrome problem.

4
00:00:08,920 --> 00:00:11,810
In this lesson I'm going to show you how
I would do it.

5
00:00:12,160 --> 00:00:17,310
The first thing that I would do is look
at the question and realize that the

6
00:00:17,320 --> 00:00:22,950
palindrome definition portion of the
question, which is where we identify if

7
00:00:22,960 --> 00:00:28,750
some string or substring in the problem
is a palindrome, is only a subproblem.

8
00:00:28,760 --> 00:00:32,730
So this goes back to what I was
mentioning earlier about how palindromes

9
00:00:32,740 --> 00:00:38,130
appear in string questions but mainly as
subproblems, not as the main problem itself.

10
00:00:38,800 --> 00:00:43,790
So yes, our question is similar to us
trying to figure out if we have a valid

11
00:00:43,800 --> 00:00:46,930
palindrome or not, but it's not the whole picture.

12
00:00:47,720 --> 00:00:49,330
The key thing that we are trying to

13
00:00:49,340 --> 00:00:55,410
figure out is looking at the string, is
there a conflict in such a way between

14
00:00:55,420 --> 00:01:00,910
two characters whereby removing one of
the characters we end up with a palindrome.

15
00:01:01,280 --> 00:01:06,010
That's actually the key thing we're
trying to solve is figuring out which

16
00:01:06,020 --> 00:01:11,410
characters in this string have the
conflict and then figuring out how to

17
00:01:11,420 --> 00:01:15,470
generate the new versions of the strings
with those characters removed.

18
00:01:15,760 --> 00:01:19,030
We then need to check if either string is
a palindrome.

19
00:01:19,040 --> 00:01:24,490
So here we can see that once we've
generated our two strings, we definitely

20
00:01:24,500 --> 00:01:28,990
need to leverage one of those three
solutions we have for figuring out if a

21
00:01:29,000 --> 00:01:32,430
string is a palindrome because we're
going to have to use one of those three

22
00:01:32,440 --> 00:01:35,110
solutions on the two generated strings.

23
00:01:35,560 --> 00:01:38,230
The other thing that we notice is that if

24
00:01:38,240 --> 00:01:43,510
this string is by default a palindrome,
meaning that we don't have to remove any

25
00:01:43,520 --> 00:01:48,490
character, we have to have some way of
checking to see if that's the case.

26
00:01:48,500 --> 00:01:50,890
So that gives us a big hint.

27
00:01:51,640 --> 00:01:53,930
Knowing that this string can be a

28
00:01:53,940 --> 00:01:59,210
palindrome means that we can probably
utilize one of those three solutions as a

29
00:01:59,220 --> 00:02:01,910
starting point to figure out an optimal solution.

30
00:02:02,520 --> 00:02:04,990
So with that in mind, let's use process

31
00:02:05,000 --> 00:02:10,270
of elimination to figure out which of
those three is most ideal to start

32
00:02:10,280 --> 00:02:12,370
applying to this string question.

33
00:02:13,140 --> 00:02:15,850
So the first thing we notice is that if

34
00:02:15,860 --> 00:02:20,910
we were to use the reverse string method,
what we do is we generate a reverse of

35
00:02:20,920 --> 00:02:21,510
this string.

36
00:02:22,020 --> 00:02:25,210
And what we do is we then compare the values.

37
00:02:25,520 --> 00:02:30,370
So here it would be A, B, D, C, C, B, A.

38
00:02:30,860 --> 00:02:33,630
Our solution then uses an equality check

39
00:02:33,640 --> 00:02:38,050
to see if these strings are equal and we
can see that they already are not.

40
00:02:38,060 --> 00:02:42,070
We know that the D and the C will
conflict, but our solution, because it's

41
00:02:42,080 --> 00:02:44,530
an equality check, doesn't actually give
us that information.

42
00:02:44,940 --> 00:02:49,210
We can visually see because we know this
string is not a palindrome, but we can

43
00:02:49,220 --> 00:02:53,310
already tell that this is not going to be
the right solution to work with because

44
00:02:53,320 --> 00:02:59,050
it gives us no information about where
the actual conflicting characters are.

45
00:02:59,260 --> 00:03:03,690
And we know that that's a key piece of
information we need because we need to

46
00:03:03,700 --> 00:03:06,810
generate strings once we know the
conflicting characters.

47
00:03:06,820 --> 00:03:12,390
So from here then, let's actually explore
the other two options because we've

48
00:03:12,400 --> 00:03:15,010
eliminated this reversal comparison solution.

49
00:03:15,540 --> 00:03:17,770
So the other two options we have is to

50
00:03:17,780 --> 00:03:22,730
generate left and right pointers either
from the center of the string or from the

51
00:03:22,740 --> 00:03:23,710
outside of the string.

52
00:03:24,520 --> 00:03:28,390
If we think about that, we know that the

53
00:03:28,400 --> 00:03:33,170
center generation is a little bit more
complicated because we do have to account

54
00:03:33,180 --> 00:03:35,290
for whether or not the string is odd or even.

55
00:03:35,980 --> 00:03:38,070
And if we think about it in those terms,

56
00:03:38,320 --> 00:03:40,830
that solution is ever so slightly more complicated.

57
00:03:41,140 --> 00:03:43,270
It doesn't actually affect the space and

58
00:03:43,280 --> 00:03:47,730
time complexity, but here let's just use
the left and right pointers from the

59
00:03:47,740 --> 00:03:49,750
outside for simplicity's sake.

60
00:03:50,040 --> 00:03:51,830
We can easily go with the other one, but

61
00:03:51,840 --> 00:03:55,890
because this one's a little simpler to
implement, it gives us less moving pieces

62
00:03:55,900 --> 00:04:00,990
to work around with because we have to
still transform the solution a little bit

63
00:04:01,000 --> 00:04:03,930
in order for it to work to this new
current problem.

64
00:04:04,780 --> 00:04:09,690
So let's say we go with that solution
where we initialize a left pointer and a

65
00:04:09,700 --> 00:04:12,930
right pointer on the outside edges of the string.

66
00:04:13,320 --> 00:04:16,190
We compare these two values, the A and

67
00:04:16,200 --> 00:04:17,690
the A, and we see that they're equal.

68
00:04:17,960 --> 00:04:20,430
So then we move the pointers inwards here.

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

70
00:04:24,600 --> 00:04:25,330
They're both B.

71
00:04:25,340 --> 00:04:28,730
So we move the pointers again, and now we

72
00:04:28,740 --> 00:04:32,210
see that we have a conflict, the C and
the D conflict.

73
00:04:32,860 --> 00:04:38,750
So what we then do is we want to generate
new strings, removing either of these characters.

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

75
00:04:46,760 --> 00:04:50,690
And then we're going to generate our
other string by removing this C.

76
00:04:50,920 --> 00:04:55,510
So we end up with A, B, C, D, B, A.

77
00:04:56,340 --> 00:04:58,670
Now that we have our two strings, we need

78
00:04:58,680 --> 00:05:01,030
to figure out if they are palindromes.

79
00:05:01,340 --> 00:05:04,230
So how we can do this is, remember with

80
00:05:04,240 --> 00:05:07,090
our original string, we've already
checked these characters.

81
00:05:07,580 --> 00:05:11,730
So we don't need to check these
characters anymore because they are not

82
00:05:11,740 --> 00:05:12,650
the ones that changed.

83
00:05:12,660 --> 00:05:15,250
The ones that changed are in the position

84
00:05:15,260 --> 00:05:16,250
of left and right.

85
00:05:16,480 --> 00:05:19,050
So at the indices that the left and right

86
00:05:19,060 --> 00:05:22,030
pointers in our original string is
pointing at.

87
00:05:22,280 --> 00:05:27,530
So we can just continue from there and
just do our checks from here while

88
00:05:27,540 --> 00:05:29,570
continuing to move inwards.

89
00:05:30,040 --> 00:05:32,090
Now I know that here we only have two

90
00:05:32,100 --> 00:05:35,630
characters left, but if there were more,
you would just check these characters,

91
00:05:35,840 --> 00:05:37,810
keep going in, check the characters, keep
going in.

92
00:05:37,820 --> 00:05:42,510
And from there, you can just say if
whatever is remaining inside of this

93
00:05:42,520 --> 00:05:46,490
string, if they match the palindrome
pattern matching, then we know that this

94
00:05:46,500 --> 00:05:47,130
is a palindrome.

95
00:05:47,520 --> 00:05:49,870
If they don't, then we know it's not a palindrome.

96
00:05:50,100 --> 00:05:52,010
There's no more characters we have left
to remove.

97
00:05:52,580 --> 00:05:55,470
So from here, we see that this is indeed matching.

98
00:05:55,800 --> 00:05:57,450
So this string is a palindrome.

99
00:05:57,900 --> 00:05:59,010
This one doesn't match.

100
00:05:59,140 --> 00:06:00,210
So it's not a palindrome.

101
00:06:00,580 --> 00:06:03,290
But because this one is, we have our answer.

102
00:06:03,300 --> 00:06:06,330
So we know that this is indeed an almost

103
00:06:06,340 --> 00:06:11,490
palindrome because one of the strings
from the character we removed became a palindrome.

104
00:06:12,580 --> 00:06:15,490
So I want to challenge you to code out
this solution.

105
00:06:15,500 --> 00:06:17,450
I will give you a hint.

106
00:06:18,160 --> 00:06:21,430
The key is going to be around passing

107
00:06:21,440 --> 00:06:27,710
this original string into some kind of
function that will then check whether or

108
00:06:27,720 --> 00:06:33,050
not we have a palindrome by passing not
only the string, but also the current

109
00:06:33,060 --> 00:06:34,050
left and right pointers.

110
00:06:34,740 --> 00:06:36,950
And one of these pointers needs to be the

111
00:06:36,960 --> 00:06:41,910
one that is technically removing the
character by shifting inwards.

112
00:06:42,640 --> 00:06:43,990
Hopefully that's enough of a hint.

113
00:06:44,540 --> 00:06:45,950
And I want to challenge you to try it out.

114
00:06:46,180 --> 00:06:49,030
In the next lesson, I'm going to show you
how we're going to code this solution.