Understanding the 'Valid Palindrome with One Deletion' Problem

The Valid Palindrome II problem requires us to determine if a string can become a valid palindrome after deleting at most one character. While checking a standard palindrome is straightforward, handling the option to delete a single character introduces branching logic that must be implemented efficiently.

Analyzing the Bottleneck in the Naive Approach

Let's look at why the original implementation suffers from poor runtime complexity:

arr = [s[x] for x in range(len(s)) if x != j]
if arr == arr[::-1]:
    return True

In the initial code, whenever a character mismatch occurs at indices i and j, new Python lists are generated using list comprehensions. Creating a list of length N takes O(N) time and space. Because this allocation happens inside the loop, the overall worst-case runtime degrades to O(N^2) with heavy memory overhead.

The Optimal Strategy: Two Pointers with One-Time Branching

To reduce the time complexity from O(N^2) down to O(N), we can use a two-pointer approach with a critical optimization: you only ever need to branch on the very first mismatch.

Here is how the linear-time algorithm works:

  • Initialize left = 0 and right = len(s) - 1.
  • Move the pointers toward each other as long as s[left] == s[right].
  • When a mismatch occurs (s[left] != s[right]), you have two choices: delete the character at left or delete the character at right.
  • Check if the remaining substring between left + 1 to right OR left to right - 1 forms a valid palindrome.
  • If either substring is a palindrome, return True; otherwise, return False.

Python Implementation (Optimal O(1) Space)

Using a helper function allows us to perform the remaining check in O(1) auxiliary space without creating duplicate string objects:

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_palindrome_range(i: int, j: int) -> bool:
            while i < j:
                if s[i] != s[j]:
                    return False
                i += 1
                j -= 1
            return True

        left, right = 0, len(s) - 1
        while left < right:
            if s[left] != s[right]:
                # Attempt deleting character at 'left' OR character at 'right'
                return is_palindrome_range(left + 1, right) or is_palindrome_range(left, right - 1)
            left += 1
            right -= 1
            
        return True

Shorter Pythonic Slicing Alternative

Since Python's string slicing is implemented in C, you can also write a clean, slice-based version that runs extremely fast in practice:

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

Complexity Analysis

  • Time Complexity: O(N). In the worst case, we traverse the string once. When a mismatch is encountered, checking the remaining substrings takes at most O(N) time, occurring at most once.
  • Space Complexity: O(1) when using pointer offsets with a helper function, or O(N) space if using Python string slicing.

Key Takeaways

By stopping unnecessary array allocations inside loops and delegating the single-deletion choice to a focused subroutine, we reduce an expensive O(N^2) algorithm into an optimal O(N) linear solution suitable for large inputs and technical interviews.