Valid Palindrome II

easy two pointers string greedy

Problem

Given a string s, return true if s can be a palindrome after deleting at most one character from it.

Inputs = "abca"

Outputtrue

Removing 'c' leaves "aba", a palindrome.

def valid_palindrome(s):
    def is_pal(i, j):
        while i < j:
            if s[i] != s[j]: return False
            i += 1; j -= 1
        return True
    i, j = 0, len(s) - 1
    while i < j:
        if s[i] != s[j]:
            return is_pal(i + 1, j) or is_pal(i, j - 1)
        i += 1; j -= 1
    return True

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

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;
    }
    boolean isPal(String s, int i, int j) {
        while (i < j) { if (s.charAt(i) != s.charAt(j)) return false; i++; j--; }
        return true;
    }
}

bool isPal(const string& s, int i, int j) {
    while (i < j) { if (s[i] != s[j]) return false; i++; j--; }
    return true;
}
bool validPalindrome(string s) {
    int i = 0, j = s.size() - 1;
    while (i < j) {
        if (s[i] != s[j]) return isPal(s, i + 1, j) || isPal(s, i, j - 1);
        i++; j--;
    }
    return true;
}

Explanation

A palindrome reads the same forwards and backwards, so the natural check is two pointers: i from the front and j from the back, comparing characters as they move inward. Here we're allowed one deletion, which we save for the first time something goes wrong.

As long as s[i] == s[j], the outer characters match and we step inward (i++, j--). If we get all the way through, the string was already a palindrome and the answer is true.

The moment we hit a mismatch at s[i] != s[j], we must spend our one allowed delete on exactly one of these two characters. So we test both options: is the substring with i skipped a palindrome (isPal(i + 1, j)), or the one with j skipped (isPal(i, j - 1))? If either is a clean palindrome, we return true.

Example: s = "abca". i=0 ('a') and j=3 ('a') match, step in. Now i=1 ('b') vs j=2 ('c') mismatch. Try skipping j: "ab"'s inner check on isPal(1, 1) succeeds (leaving "aba"), so the answer is true.

The helper isPal only runs once, on the leftover middle after a single mismatch, so the whole thing stays linear in the length of the string.

Time: O(n) Space: O(1)