Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Valid Palindrome II.js

//Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
//https://leetcode.com/explore/interview/card/facebook/5/round-1-phone-interview/289/

//Solution 1 - Not efficient o(n^2)
//---------------------------------------------------
var validPalindrome = function(s) {
    for (let i = 0; i < s.length; i++) {
        let w = s.substr(0, i) + s.substr(i + 1);
        if (isPal(w)) {
            return true;
        }
    }
    return isPal(s);
};

function isPal(str) {
    if (!str || str.length === 0) return true;
    return [...str].reverse().join("") === str;
}


//Solution 2 - efficient o(n)
//---------------------------------------------------
var validPalindrome = function(s) {
    let left = 0, right = s.length - 1;
    while (left < right) {
        if (s[left] === s[right]) {
            left++;
            right--;
        } else {
            return helper(s, left + 1, right) || helper(s, left, right - 1);
        }
    }
    
    return true;
};

function helper(s, left, right) {
    while (left < right) {
        if (s[left] !== s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}