LeetCode 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


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


Use two pointers technique. One pointer starts from the beginning, one starts from the end. Whenever two pointers found two unmatched characters, skip the character from either side to see if the remaining parts fits the palindrome requirement.

Python Solution

class Solution:
    def validPalindrome(self, s: str) -> bool:
        i = 0
        j = len(s) - 1
        while i < j:
            if s[i] == s[j]:
                i += 1
                j -= 1
                return self.helper(s, i + 1, j) or self.helper(s, i, j - 1)

        return True
    def helper(self, s, left, right):
        while left < right:
            if s[left] == s[right]:
                left += 1
                right -= 1
                return False
        return True
  • Time Complexity: O(N).
  • Space Complexity: O(1).

Leave a Reply

Your email address will not be published. Required fields are marked *