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:

`Input: s = "aba"Output: true`

Example 2:

`Input: s = "abca"Output: trueExplanation: 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.

--

--

--

More from Jaydeep

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

Love podcasts or audiobooks? Learn on the go with our new app.

Jaydeep

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