Approach: Two pointers with one skip

def validPalindrome(s):
    def isPal(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 isPal(i+1, j) or isPal(i, j-1)
        i += 1; j -= 1
    return True

Complexity: O(n) time, O(1) space.

Full Solution — all languages

class Solution:
    def validPalindrome(self, s):
        def isPal(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 isPal(i + 1, j) or isPal(i, j - 1)
            i += 1
            j -= 1
        return True

import java.util.*;
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;
    }
}

#include <bits/stdc++.h> using namespace std;
class Solution {
    public: bool validPalindrome(string s) {
        auto isPal = [&](int i, int j) {
            while (i < j) {
                if (s[i] != s[j]) return false;
                i++;
                j--;
            }
            return true;
        };
        int i = 0, j = (int)s.size() - 1;
        while (i < j) {
            if (s[i] != s[j]) return isPal(i + 1, j) || isPal(i, j - 1);
            i++;
            j--;
        }
        return true;
    }
};

/**
 * @param {string} s
 * @return {boolean}
 */ var validPalindrome = function(s) {
    const 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;
};

Valid Palindrome II

Example 1

Example 2

Example 3

Constraints