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 sub problem.
So this goes back to what I was mentioning earlier about how palindromes appear in string questions,
but mainly as sub problems, 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 where by 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, C, C, B, A, our solution then uses and a quality check to see if these
strings are equal and we can see that they already are not.
We know that the D in the sea will conflict, but our solution, because it's in a quality check, doesn't
actually give us that information we can visually see because we know the 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 oter 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 the other one.
But because this one's a little simpler to implement, it gives us the 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
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 that we move the pointers
inwards here.
And when we compare these new characters, we see they're still equal, they're both be.
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 than we ever 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 it 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 character 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 coat 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, bypassing 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 the solution.