LeetCode 680: Valid Palindrome II

Problem Description

LeetCode Problem 680

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.

Difficulty: Easy

Tags: two pointers, string, greedy

Rating: 94.77%

Implementation

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def isPalindrome(s):
            return s == s[::-1]
        
        l, r = 0, len(s)-1
        while l < r:
            if s[l] != s[r]:
                return isPalindrome(s[l+1:r+1]) or isPalindrome(s[l:r])
            l += 1
            r -= 1
        return True 

Step-by-Step Walkthrough

Let’s walk through the example "abca":

1. Initial state:

   a  b  c  a
   ↑        ↑
   l        r
   

   • Compare s[l] (‘a’) with s[r] (‘a’) → Match
   • Move pointers: l++, r--

2. After first iteration:

   a  b  c  a
      ↑  ↑
      l  r
   

   • Compare s[l] (‘b’) with s[r] (‘c’) → Mismatch!
   • Try two possibilities:
     • Remove ‘b’: Check if “aca” is palindrome
     • Remove ‘c’: Check if “aba” is palindrome

3. Result:

   • “aba” is a palindrome
   • Return true

Complexity Analysis

• Time Complexity: $O(n)$

  • We traverse the string once with two pointers
  • In worst case, we check two substrings of length n-1

• Space Complexity: $O(1)$

  • We only use constant extra space for pointers
  • String slicing in Python creates new strings, but we can optimize this if needed