Valid Palindrome II

You're given a string s of lowercase letters. You may delete at most one character from it, anywhere.

Return true if the string can read the same forwards and backwards after that, and false otherwise. A string that is already a palindrome counts as true with no deletion.

Checking a palindrome is two pointers walking inward and comparing. As long as the characters match, there is nothing to decide: deleting a matched character would never help.

The first mismatch, at positions left and right, is the only place a deletion can go. One of those two characters must be the extra one, so there are exactly two candidates: skip s[left] and check whether s[left+1..right] is a palindrome, or skip s[right] and check s[left..right-1]. If either works, the answer is true. No further deletions are allowed, so those inner checks are plain palindrome checks.

def valid_palindrome(s: str) -> bool:
    def is_pal(lo: int, hi: int) -> bool:
        while lo < hi:
            if s[lo] != s[hi]:
                return False
            lo += 1
            hi -= 1
        return True

    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            # The extra character is one of these two.
            return is_pal(left + 1, right) or is_pal(left, right - 1)
        left += 1
        right -= 1
    return True

function validPalindrome(s) {
  const isPal = (lo, hi) => {
    while (lo < hi) {
      if (s[lo] !== s[hi]) return false;
      lo++;
      hi--;
    }
    return true;
  };

  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    if (s[left] !== s[right]) {
      // The extra character is one of these two.
      return isPal(left + 1, right) || isPal(left, right - 1);
    }
    left++;
    right--;
  }
  return true;
}

Explain why the mismatch is the only decision point: matched outer characters are safe to keep, so the deletion has to be one of the two mismatched characters. That one sentence justifies the whole algorithm.

Then show a case where each side is the right one ("abbab" and "babba"). Interviewers often probe whether a greedy "always skip left" works, and having those two examples ready answers it immediately.