Valid Palindrome II

Problem

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

 

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

 

Constraints:

• 1 <= s.length <= 105
• s consists of lowercase English letters.

Solution

/**
 * @param {string} s
 * @return {boolean}
 */
var validPalindrome = function(s) {
    let l = 0;
    let r = s.length - 1;

    while (l < r) {
        if (s[l] !== s[r]) {
            return isPalindrome(s, l + 1, r) || isPalindrome(s, l, r - 1);
        }
        l++;
        r--;
    }
    return true;
};

var isPalindrome = function(s, l, r) {
    while (l < r) {
        if (s[l++] !== s[r--]) {
            return false;
        }
    }
    return true;
};

We will implement a two pointers solution. We use the standard two pointers method of checking if s is a palindrome (ie. use indices l and r to slide inwards and check if s[l] == s[r]). The only difference is that on the first s[l] and s[r] that is different, we don't immediately terminate. Instead, since we can skip a single letter, we test whether skipping either s[l] or s[r] would give us a valid palindrome.