Valid Palindrome II (At Most One Deletion)

Problem

Given a string, check if it can become a palindrome after deleting at most one character.

Input:  s = "abca"
Output: true   (delete 'c' or 'b' to get "aba" or "aca")

Python Solution

def valid_palindrome_ii(s):
    def is_palindrome_range(left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return is_palindrome_range(left + 1, right) or is_palindrome_range(left, right - 1)
        left += 1
        right -= 1
    return True

C++ Solution

bool isPalindromeRange(string& s, int left, int right) {
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++; right--;
    }
    return true;
}

bool validPalindromeII(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;
}

Java Solution

class Solution {
    public boolean validPalindromeII(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 left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++; right--;
        }
        return true;
    }
}

Complexity

Time: O(n) — the first scan is O(n), and on the first mismatch, at most two O(n) checks are done, so the total stays linear. Space: O(1) — only pointers are used, no extra structure.