281. Valid Palindrome II

Walk two pointers inward while characters match. At the first mismatch you get exactly one deletion — either skip the left character or the right one — so check whether the remaining inner substring is a plain palindrome in either case.

Converge, then branch once

Use two pointers i (left) and j (right) moving toward the center. As long as s[i] == s[j], keep going — those characters are fine.

Handling the first mismatch

When s[i] != s[j], your single allowed deletion must remove either s[i] or s[j]. So test both leftover ranges as ordinary palindromes:

isPalindrome(i+1, j)   # deleted s[i]
isPalindrome(i, j-1)   # deleted s[j]

If either is a palindrome, the whole string works with one deletion → return true. If neither is, one deletion can't fix it → false. If the pointers meet without any mismatch, it was already a palindrome (zero deletions).

i, j = 0, n-1
while i < j:
    if s[i] != s[j]:
        return isPalindrome(i+1, j) or isPalindrome(i, j-1)
    i += 1; j -= 1
return True

Worked example

s = "abca".

• i=0(a), j=3(a) match → move in.
• i=1(b), j=2(c) mismatch. Try deleting b → check "c" (isPalindrome(2,2)) → palindrome ✓.

Return true (delete b, leaving "aca").

Complexity

• Time: O(n) — one pass, plus at most one linear palindrome check.
• Space: O(1).

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

    private boolean isPal(String s, int i, int j) {
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
}