Valid Palindrome II [Medium] — Delete At Most One Character

Problem Statement

Return true if the string can be a palindrome after deleting at most one character.

Input: "aba"  → true
Input: "abca" → true (delete 'c')
Input: "abc"  → false

Intuition

Two pointers from ends. When mismatch found, try skipping left or skipping right character — if either remaining substring is a palindrome, return true.

Solutions

C++

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

Java

public boolean validPalindrome(String s) {
    int l=0, r=s.length()-1;
    while(l<r){
        if(s.charAt(l)!=s.charAt(r)) return isPalin(s,l+1,r)||isPalin(s,l,r-1);
        l++;r--;
    }
    return true;
}
boolean isPalin(String s,int l,int r){
    while(l<r)if(s.charAt(l++)!=s.charAt(r--))return false;return true;
}

Python

def validPalindrome(s: str) -> bool:
    def is_palin(l, r):
        while l < r:
            if s[l] != s[r]: return False
            l += 1; r -= 1
        return True
    l, r = 0, len(s)-1
    while l < r:
        if s[l] != s[r]:
            return is_palin(l+1, r) or is_palin(l, r-1)
        l += 1; r -= 1
    return True

Complexity

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