Valid Palindrome II Solution

Problem

Given a string, determine whether you can make it a palindrome by deleting at most one character. The remaining characters must read the same forwards and backwards.

Input: s = "abca"
Output: true
Explanation: Removing 'c' at index 2 yields "aba", which is a palindrome.

Counter-example: s = "abc" → false. Removing 'a' gives "bc", removing 'b' gives "ac", removing 'c' gives "ab" — none are palindromes.

Intuition

Without any deletion, a two-pointer check starting from both ends catches mismatches immediately. The extra twist here is that the first mismatch you hit triggers your one allowed deletion: you can skip either the left character or the right character, then verify the remaining substring is a full palindrome. If either choice works, the answer is true.

Approach 1 — Try Every Deletion

For each index, remove that character and check if the resulting string is a palindrome. Return true if any removal works.

Loop over every index i.
Form a candidate string by removing s[i].
Check whether the candidate equals its reverse.
Return true at the first palindrome found; return false if none is found after all deletions.

1class Solution:
2    def validPalindrome(self, s: str) -> bool:
3        def is_palindrome(string: str) -> bool:
4            return string == string[::-1]
5
6        for i in range(len(s)):
7            candidate = s[:i] + s[i + 1:]  # remove character at index i
8            if is_palindrome(candidate):
9                return True
10        return False

Time: O(n²) — n candidate strings, each requiring an O(n) palindrome check. Space: O(n) — each candidate is a new string of length n − 1.

Approach 2 — Two Pointers with One Skip

Use two pointers advancing from both ends. When characters match, move both inward. When a mismatch is found, apply the one allowed deletion by checking both options — skip left or skip right — using index bounds so no new string is allocated.

Set left = 0, right = len(s) - 1.
Advance both pointers inward while characters match.
On a mismatch, call the palindrome helper on s[left+1..right] and on s[left..right-1].
Return true if either half-range is a palindrome; return false if neither is.
If the outer loop finishes with no mismatch, the string is already a palindrome — return true.

1class Solution:
2    def validPalindrome(self, s: str) -> bool:
3        def is_palindrome_range(left: int, right: int) -> bool:
4            while left < right:
5                if s[left] != s[right]:
6                    return False
7                left += 1
8                right -= 1
9            return True
10
11        left, right = 0, len(s) - 1
12        while left < right:
13            if s[left] != s[right]:
14                # try skipping the left character or the right character
15                return is_palindrome_range(left + 1, right) or \
16                       is_palindrome_range(left, right - 1)
17            left += 1
18            right -= 1
19        return True  # already a palindrome — no deletion was needed

Time: O(n) — the outer pass and both inner checks together examine at most 2n characters total. Space: O(1) — only index variables; no extra strings are created.

Complexity Summary

Approach	Time	Space	When to use
Try Every Deletion	O(n²)	O(n)	Only for very short strings or quick prototyping
Two Pointers with One Skip	O(n)	O(1)	Always — handles strings up to 500,000 characters efficiently

Common Mistakes

Checking only one skip direction — when a mismatch is found, both s[left+1..right] and s[left..right-1] must be checked; the first option could fail while the second succeeds (e.g. "cbbca" at mismatch: skipping left gives "bbca" which fails, skipping right gives "cbbc" which passes).
Allowing a second skip inside the inner check — the helper must be a strict palindrome check with no further deletions; calling validPalindrome recursively here would silently permit two total deletions.
Mixing this up with the original Valid Palindrome — that problem strips non-alphanumeric characters and lowercases; this problem uses the raw string as-is with no such preprocessing.
Allocating a new substring in the inner check — slicing (e.g. s[left+1:right+1]) creates a new O(n) string on each call; pass index bounds to the helper instead to keep space constant.
Returning false at the end of the main loop — if the loop finishes with no mismatch, the string was already a palindrome and the function should return true, not false.

Valid Palindrome II — Solution