Solution 1 - Two Pointers + One Deletion

On first mismatch, check if skipping either endpoint yields a palindrome.

TimeComplexity: O(n)

SpaceComplexity: O(1)

""" 0680.1 - Valid Palindrome II - Solution 1 - Two Pointers """

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_pal(i: int, j: int) -> bool:
            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 and s[i] == s[j]:
            i += 1
            j -= 1

        return is_pal(i + 1, j) or is_pal(i, j - 1)

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

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

package main

func validPalindrome(s string) bool {
	isPal := func(i, j int) bool {
		for i < j {
			if s[i] != s[j] {
				return false
			}
			i++
			j--
		}
		return true
	}
	i, j := 0, len(s)-1
	for i < j && s[i] == s[j] {
		i++
		j--
	}
	return isPal(i+1, j) || isPal(i, j-1)
}

func main() {}

fn valid_palindrome(s: &str) -> bool {
	let b = s.as_bytes();
	let is_pal = |mut i: usize, mut j: usize| -> bool {
		while i < j {
			if b[i] != b[j] { return false; }
			i += 1; j -= 1;
		}
		true
	};
	let (mut i, mut j) = (0usize, b.len().saturating_sub(1));
	while i < j && b[i] == b[j] { i += 1; j -= 1; }
	is_pal(i+1, j) || is_pal(i, j.saturating_sub(1))
}
fn main() {}

0680 - Valid Palindrome II

Solution 1 - Two Pointers + One Deletion