Code Implementation

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_palindrome_range(i, j):
            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]:
                # Try skipping either the left or the right character
                return is_palindrome_range(left+1, right) or is_palindrome_range(left, right-1)
            left += 1
            right -= 1
        return True
      

class Solution {
public:
    bool isPalindromeRange(const std::string& s, int i, int j) {
        while (i < j) {
            if (s[i] != s[j]) return false;
            ++i;
            --j;
        }
        return true;
    }

    bool validPalindrome(std::string s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            if (s[left] != s[right]) {
                return isPalindromeRange(s, left+1, right) || isPalindromeRange(s, left, right-1);
            }
            ++left;
            --right;
        }
        return true;
    }
};
      

class Solution {
    public boolean validPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return isPalindromeRange(s, left + 1, right) || isPalindromeRange(s, left, right - 1);
            }
            left++;
            right--;
        }
        return true;
    }
    private boolean isPalindromeRange(String s, int i, int j) {
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
}
      

var validPalindrome = function(s) {
    function isPalindromeRange(i, j) {
        while (i < j) {
            if (s[i] !== s[j]) return false;
            i++;
            j--;
        }
        return true;
    }
    let left = 0, right = s.length - 1;
    while (left < right) {
        if (s[left] !== s[right]) {
            return isPalindromeRange(left + 1, right) || isPalindromeRange(left, right - 1);
        }
        left++;
        right--;
    }
    return true;
};
      

Problem Description

Given a string s, determine if it can become a palindrome after deleting at most one character. A palindrome is a string that reads the same forwards and backwards. You may only remove one character, or none at all. The function should return true if it's possible to make s a palindrome with at most one deletion, and false otherwise.

• Only one character may be removed at most.
• Input s consists of lowercase letters and may be up to 10⁵ characters long.
• Return true if possible, false if not.

Thought Process

The classic way to check if a string is a palindrome is to use two pointers, one starting at the beginning and one at the end, comparing characters as they move towards the center. If all characters match, it's a palindrome.

The twist here is that you are allowed to remove at most one character. That means, if you find a mismatch, you have two choices: skip the character on the left or skip the character on the right, and check if the remaining substring is a palindrome. If either option works, the answer is true.

Brute-forcing by removing every character one-by-one and checking for a palindrome would be too slow for large strings. Instead, we can optimize by only checking the two possible substrings when we find the first mismatch.

Solution Approach

• Step 1: Start with two pointers, left at the start of the string and right at the end.
• Step 2: While left < right, compare s[left] and s[right].
  • If they match, move both pointers closer to the center.
  • If they don't match, try skipping either left or right character:
    • Check if the substring s[left+1:right+1] is a palindrome.
    • Check if the substring s[left:right] is a palindrome.
    • If either is true, return true.
• Step 3: If the loop completes with no mismatches, or a valid removal is found, return true. Otherwise, return false.
• Why this works: We only ever need to check two possible substrings when a mismatch occurs, which keeps the solution efficient.

Example Walkthrough

Let's use the example s = "abca":

• Step 1: left = 0, right = 3. s[0] = 'a', s[3] = 'a'. They match, move pointers inwards.
• Step 2: left = 1, right = 2. s[1] = 'b', s[2] = 'c'. Mismatch!
• Now, try removing one character:
  • Skip 'b' (left+1): Check if "ca" is a palindrome. It's not.
  • Skip 'c' (right-1): Check if "ba" is a palindrome. It's not.
  • But, actually, check the substrings:
    • s[1:3] = "bc" (not palindrome)
    • s[0:2] = "ab" (not palindrome)
    • Wait, but with our method, we check s[2:3] = "c" and s[1:2] = "b", both are palindromes because a single character is always a palindrome. So, the function would return true.
• Result: It's possible to make "abca" a palindrome by removing either 'b' or 'c'.

Time and Space Complexity

• Brute-force approach: For each character, remove it and check if the rest is a palindrome. That's O(n^2) time and O(n) space per check (for substring).
• Optimized two-pointer approach:
  • We traverse the string once (O(n)).
  • At most, we make two more passes (at the point of mismatch) over a substring (O(n) total).
  • Overall time complexity: O(n)
  • Space complexity: O(1) (if implemented using indices, not slicing substrings).

Summary

This problem is a great example of how a small twist (allowing one removal) changes the classic palindrome check. By using a two-pointer technique and only checking the two possible substrings at the point of mismatch, we achieve an efficient O(n) solution. The key insight is that only one removal is allowed, so we only need to check two possible cases when a mismatch occurs, making the approach both elegant and optimal.