Valid Palindrome II

How it works

The previous two-pointer solution creates new substrings, which costs O(n) space. We can optimize this by passing index bounds to our palindrome check function instead of creating new strings. This way, we check the same characters without allocating extra memory. The logic remains identical: find the first mismatch, then verify if skipping either character leads to a valid palindrome.

Steps

1. Create a helper function isPalindrome(l, r) that checks if s[l...r] is a palindrome using two pointers without creating a new string.
2. Initialize pointers l = 0 and r = len(s) - 1.
3. While l < r:
   • If s[l] != s[r], return isPalindrome(l+1, r) or isPalindrome(l, r-1).
   • Otherwise, increment l and decrement r.
4. Return true if the loop completes (string is already a palindrome).

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Only Trying One Deletion Option

When a mismatch is found at positions l and r, you must check both possibilities: removing the character at l or removing the character at r. A common mistake is only trying one option (like always removing the left character). Both substrings s[l+1...r] and s[l...r-1] must be checked, and the answer is true if either forms a palindrome.

Forgetting That Zero Deletions Is Valid

The problem asks if the string can become a palindrome by deleting at most one character. This includes deleting zero characters. If the original string is already a palindrome, the answer is true. Some solutions only consider the deletion case and forget to check if the string is already valid as-is.

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_palindrome(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_palindrome(l + 1, r) or
                        is_palindrome(l, r - 1))
            l += 1
            r -= 1

        return True

class Solution {
public:
    bool validPalindrome(string s) {
        int l = 0, r = s.size() - 1;

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

        return true;
    }

private:
    bool isPalindrome(const string& s, int l, int r) {
        while (l < r) {
            if (s[l] != s[r]) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
};