Valid Palindrome II

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

Example 1:

Example 2:

Example 3:

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.

Full Stack Programmer, love to solve problem’s during free time.

More from Jaydeep

Full Stack Programmer, love to solve problem’s during free time.