Hello everyone and welcome back.
Hopefully you got a chance to try and
come up with a solution and code it yourself for our almost palindrome problem.
In this lesson I'm going to show you how I would do it.
The first thing that I would do is look at the question and realize that the
palindrome definition portion of the question, which is where we identify if
some string or substring in the problem is a palindrome, is only a subproblem.
So this goes back to what I was mentioning earlier about how palindromes
appear in string questions but mainly as subproblems, not as the main problem itself.
So yes, our question is similar to us trying to figure out if we have a valid
palindrome or not, but it's not the whole picture.
The key thing that we are trying to
figure out is looking at the string, is there a conflict in such a way between
two characters whereby removing one of the characters we end up with a palindrome.
That's actually the key thing we're trying to solve is figuring out which
characters in this string have the conflict and then figuring out how to
generate the new versions of the strings with those characters removed.
We then need to check if either string is a palindrome.
So here we can see that once we've generated our two strings, we definitely
need to leverage one of those three solutions we have for figuring out if a
string is a palindrome because we're going to have to use one of those three
solutions on the two generated strings.
The other thing that we notice is that if
this string is by default a palindrome, meaning that we don't have to remove any
character, we have to have some way of checking to see if that's the case.
So that gives us a big hint.
Knowing that this string can be a
palindrome means that we can probably utilize one of those three solutions as a
starting point to figure out an optimal solution.
So with that in mind, let's use process
of elimination to figure out which of those three is most ideal to start
applying to this string question.
So the first thing we notice is that if
we were to use the reverse string method, what we do is we generate a reverse of
this string.
And what we do is we then compare the values.
So here it would be A, B, D, C, C, B, A.
Our solution then uses an equality check
to see if these strings are equal and we can see that they already are not.
We know that the D and the C will conflict, but our solution, because it's
an equality check, doesn't actually give us that information.
We can visually see because we know this string is not a palindrome, but we can
already tell that this is not going to be the right solution to work with because
it gives us no information about where the actual conflicting characters are.
And we know that that's a key piece of information we need because we need to
generate strings once we know the conflicting characters.
So from here then, let's actually explore the other two options because we've
eliminated this reversal comparison solution.
So the other two options we have is to
generate left and right pointers either from the center of the string or from the
outside of the string.
If we think about that, we know that the
center generation is a little bit more complicated because we do have to account
for whether or not the string is odd or even.
And if we think about it in those terms,
that solution is ever so slightly more complicated.
It doesn't actually affect the space and
time complexity, but here let's just use the left and right pointers from the
outside for simplicity's sake.
We can easily go with the other one, but
because this one's a little simpler to implement, it gives us less moving pieces
to work around with because we have to still transform the solution a little bit
in order for it to work to this new current problem.
So let's say we go with that solution where we initialize a left pointer and a
right pointer on the outside edges of the string.
We compare these two values, the A and
the A, and we see that they're equal.
So then we move the pointers inwards here.
And when we compare these new characters, we see they're still equal.
They're both B.
So we move the pointers again, and now we
see that we have a conflict, the C and the D conflict.
So what we then do is we want to generate new strings, removing either of these characters.
So here we're going to generate A, B, C, C, B, A from removing this D right here.
And then we're going to generate our other string by removing this C.
So we end up with A, B, C, D, B, A.
Now that we have our two strings, we need
to figure out if they are palindromes.
So how we can do this is, remember with
our original string, we've already checked these characters.
So we don't need to check these characters anymore because they are not
the ones that changed.
The ones that changed are in the position
of left and right.
So at the indices that the left and right
pointers in our original string is pointing at.
So we can just continue from there and just do our checks from here while
continuing to move inwards.
Now I know that here we only have two
characters left, but if there were more, you would just check these characters,
keep going in, check the characters, keep going in.
And from there, you can just say if whatever is remaining inside of this
string, if they match the palindrome pattern matching, then we know that this
is a palindrome.
If they don't, then we know it's not a palindrome.
There's no more characters we have left to remove.
So from here, we see that this is indeed matching.
So this string is a palindrome.
This one doesn't match.
So it's not a palindrome.
But because this one is, we have our answer.
So we know that this is indeed an almost
palindrome because one of the strings from the character we removed became a palindrome.
So I want to challenge you to code out this solution.
I will give you a hint.
The key is going to be around passing
this original string into some kind of function that will then check whether or
not we have a palindrome by passing not only the string, but also the current
left and right pointers.
And one of these pointers needs to be the
one that is technically removing the character by shifting inwards.
Hopefully that's enough of a hint.
And I want to challenge you to try it out.
In the next lesson, I'm going to show you how we're going to code this solution.