Valid Palindrome II

Try deleting each character from the string one at a time and check if the resulting string is a palindrome. Also check the original string itself.

1. 1Check if the original string is already a palindrome.
2. 2For each index i, build s[:i] + s[i+1:] (delete character at i).
3. 3If any resulting string is a palindrome, return True.
4. 4If none work, return False.

Why it's not optimal: O(n²) — each deletion creates an O(n) string, and we check up to n deletions. The two-pointer approach is O(n) by only checking the mismatch point.

def validPalindrome(s):
    def isPalin(t):
        return t == t[::-1]
    if isPalin(s): return True
    for i in range(len(s)):
        if isPalin(s[:i] + s[i+1:]):
            return True
    return False

Use two pointers from both ends. Match characters and move inward. On the first mismatch, we have one deletion budget — try skipping the left character or the right character and check if the remaining substring is a palindrome.

1. 1Start L=0, R=n-1. Move inward while characters match.
2. 2On mismatch, check isPalin(L+1, R) (skip left) and isPalin(L, R-1) (skip right).
3. 3If either check passes, return True.
4. 4If pointers meet without mismatch, the string is already a palindrome.