Skip to content

680. Valid Palindrome II

Two Pointers String Greedy

Problem - Valid Palindrome II

Easy

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.

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def validPalindrome(self, s: str) -> bool:
        i, j = 0, len(s) - 1
        def check_removal(i, j):
            while j > i:
                if s[i] != s[j]:
                    return False
                i, j = i + 1, j - 1
            return True

        while j > i:
            if s[i] != s[j]:
                return check_removal(i + 1, j) or check_removal(i, j - 1)
            i, j = i + 1, j - 1

        return True

Submission Stats:

  • Runtime: 66 ms (35.65%)
  • Memory: 17.8 MB (72.82%)