Palindrome check problems are very common in the Strings section of the interview process. This question is a modified version of the palindrome check on a string.
The Problem
Given a string s, return true if the string can be palindrome after deleting at most one character from it.
Example 1:
1
2
Input: s = "aba"
Output: true
Example 2:
1
2
3
Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.
Example 3:
1
2
Input: s = s = "abc"
Output: false
The Solution
To check a string is almost palindrome, we first need to understand how to check a string is a palindrome first. There are multiple ways of doing it. Create a copy of the string in reverse order and check all the characters in the same positions of strings are equal. Start two different pointers one from starting of the string and another from the end of the string. Check if the character at the pointer positions. If they are matching and move the pointers together inwards step by step until they meet. The two-pointer method can also be implemented from the middle of the string by moving pointers outwards too.
The two-pointer inward method implemented in code would look like,
Here s the string, left is the starting position and right is the ending position of the string.
Now to check the string is almost palindrome, we should do a process similar to the above but as soon as we see the first unmatching case, we should check if the string will become palindrome by eliminating either one of the characters at the pointer positions. Here one advantage we have is we only have to check the remaining part of the string since the other part is already verified. To write a code solution for this let’s make use of the above function as well.
The time complexity of this solution will be O(n).
References