# 680. 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: 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.

Solution1:

We can use the standard two-pointer approach that starts at the left and right of the string and move inwards. Whenever there is a mismatch, we can either exclude the character at the left or the right pointer. We then take the two remaining substrings and compare them against their reversed and see if either one is a palindrome.

``````class Solution(object):
def validPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
# Time: O(n)
# Space: O(n)
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
one, two = s[left:right], s[left + 1:right + 1]
return one == one[::-1] or two == two[::-1]
left, right = left + 1, right - 1
return True``````

Solution2:

``````class Solution:
def validPalindrome(self, s):
i = 0
j = len(s)-1
while i < j:
if s[i] != s[j]:
delete_i = s[i+1:j+1]
delete_j = s[i:j]
return self._isPalindrome(delete_i) or self._isPalindrome(delete_j)
i += 1
j -= 1
return True

def _isPalindrome(self, s):
return s == s[::-1]``````
Scroll to Top