Valid palindrome II

Close in from both ends as in a plain palindrome check, but the first mismatch gets one free pass: try skipping either side.

The idea

A normal two-pointer palindrome check fails at the first mismatch. Here that mismatch is not fatal: one of the two characters could be the single character allowed to be removed. Checking whether the remaining string is a palindrome with the left one skipped, or with the right one skipped, covers both possibilities.

Code

public static bool ValidPalindrome(string s) {
    int l = 0, 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;
}

static bool IsPalindrome(string s, int l, int r) {
    while (l < r) {
        if (s[l] != s[r]) return false;
        l++; r--;
    }
    return true;
}

Tips

• The two inner checks use the same ordinary IsPalindrome; nothing new is needed beyond calling it twice.
• If both skips still fail, the mismatch cannot be repaired by removing just one character.

In the .NET library

This is a small but common extension of the two-pointer palindrome pattern: allow bounded "damage" by branching into sub-checks only at the point where the plain version would have given up.