# Valid Palindrome II Problem

0 like 0 dislike
152 views

Given a non-empty string `s`, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

```Input: "aba"
Output: True
```

Example 2:

```Input: "abca"
Output: True
Explanation: You could delete the character 'c'.
```

Note:

1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

### For Indian Students- INR 360/- || For International Students- \$9.99/-

S.No.

Course Name

Coupon

1.

Tensorflow 2 & Keras:Deep Learning & Artificial Intelligence

Apply Coupon

2.

Natural Language Processing-NLP with Deep Learning in Python Apply Coupon

3.

Computer Vision OpenCV Python | YOLO| Deep Learning in Colab Apply Coupon

0 like 0 dislike
by Goeduhub's Expert (2.3k points)

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 against its 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

eg : ans = Solution()

ans.validPalindrome("abca")

Output -

True