Valid Palindrome II

Photo by Sangga Rima Roman Selia on Unsplash

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

Constraints:

• 1 <= s.length <= 105
• s consists of lowercase English letters.

Solution

1. Initialize the left and right pointers at each end of the array, respectively.
2. Traverse the array until left is less than right.
3. If the element pointed to by the left pointer is equal to the element pointed to by the right pointer, do the following:

• Increment the left pointer by one position.
• Decrement the right pointer by one position.

4. If the element pointed to by the left pointer is not equal to the element pointed to by the right pointer, do the following:

• Ignore the value at the left pointer by checking if the elements at indexes left + 1 to right form a palindrome or not. If they do, return true; this indicates the presence of only one diversion router.
• Ignore the value at the right pointer by checking if the elements at indexes left to right - 1 form a palindrome or not. If they do, return true; this indicates the presence of only one diversion router.

5. If both of the above cases fail, return false; this indicates the presence of multiple diversion routers.

6. If no mismatch occurs, return true; this indicates the presence of a zero-diversion router.

Time complexity

The time complexity will be O(n) because the array is only traversed once.

Space complexity

The space complexity will be O(1) because we only manipulate some pointers.