LeetCode 680: Valid Palindrome II

Problem Restatement

We are given a string s.

We need to return true if s can become a palindrome after deleting at most one character. Otherwise, return false. The string may also already be a palindrome, because deleting zero characters is allowed. The constraints say 1 <= s.length <= 10^5, and s contains lowercase English letters.

A palindrome reads the same from left to right and right to left.

For example:

"aba"

is a palindrome.

This string:

"abca"

can become a palindrome by deleting 'c':

"aba"

So the answer is true.

Input and Output

Item	Meaning
Input	A string `s`
Output	`true` if `s` can become a palindrome after deleting at most one character
Allowed deletion	Zero or one character
Constraint	`s` contains lowercase English letters

Example function shape:

def validPalindrome(s: str) -> bool:
    ...

Examples

Example 1:

s = "aba"

This is already a palindrome.

Answer:

True

Example 2:

s = "abca"

The first and last characters match:

a == a

The middle part is:

bc

There is a mismatch between 'b' and 'c'.

We can delete 'c', giving:

aba

Answer:

True

Example 3:

s = "abc"

Try deleting one character:

Delete	Result	Palindrome?
`'a'`	`"bc"`	No
`'b'`	`"ac"`	No
`'c'`	`"ab"`	No

Answer:

False

First Thought: Delete Each Character

A direct solution is to try every possible deletion.

For each index i, remove s[i], then check whether the remaining string is a palindrome.

Also check the original string, since zero deletions are allowed.

This works, but it is too slow.

If s has length n, there are n possible deletions. Each palindrome check takes O(n) time.

So the total time is:

O(n^2)

Since n can be as large as 10^5, this is not good enough.

Key Insight

A normal palindrome check uses two pointers:

Pointer	Starts at
`left`	Beginning of the string
`right`	End of the string

While the characters match, we move inward.

The only interesting moment is the first mismatch.

Suppose:

s[left] != s[right]

If the string can be fixed with at most one deletion, then we must delete either:

Choice	Meaning
`s[left]`	Skip the left mismatched character
`s[right]`	Skip the right mismatched character

No other deletion can fix this mismatch, because all outer characters before this point already matched.

So we only need to check two remaining substrings:

s[left + 1 : right + 1]
s[left : right]

If either substring is a palindrome, the answer is true.

Algorithm

Use a helper function:

is_palindrome_range(left, right)

This checks whether s[left:right + 1] is a palindrome without creating a new substring.

Main algorithm:

Set left = 0.
Set right = len(s) - 1.
While left < right:
- If s[left] == s[right], move both pointers inward.
- Otherwise, check:
  - whether s[left + 1:right + 1] is a palindrome
  - whether s[left:right] is a palindrome
- Return true if either check is true.
If the loop finishes, the original string is already a palindrome, so return true.

Walkthrough

Consider:

s = "abca"

Start:

Step	`left`	`right`	Characters	Result
1	0	3	`'a'` and `'a'`	Match
2	1	2	`'b'` and `'c'`	Mismatch

At the mismatch, we try two choices.

Delete left character 'b':

aca

This is a palindrome.

Delete right character 'c':

aba

This is also a palindrome.

Since at least one choice works, return true.

Now consider:

s = "abc"

Start:

Step	`left`	`right`	Characters	Result
1	0	2	`'a'` and `'c'`	Mismatch

Try deleting 'a':

bc

Not a palindrome.

Try deleting 'c':

ab

Not a palindrome.

Return false.

Correctness

The algorithm compares characters from both ends toward the center.

As long as s[left] == s[right], those two characters can remain in the final palindrome. They do not require deletion.

The first time we find a mismatch, the final valid palindrome, if it exists, must remove one of the two mismatched characters.

It cannot remove a character strictly inside the range, because then s[left] and s[right] would still remain at opposite ends and still fail to match.

It cannot remove a character outside the range, because all outside pairs have already matched.

Therefore, the only possible repairs are skipping s[left] or skipping s[right].

The helper checks exactly those two remaining ranges.

If either range is a palindrome, then deleting the corresponding mismatched character gives a valid palindrome.

If neither range is a palindrome, then no single deletion can fix the string.

If no mismatch ever occurs, the original string is already a palindrome, and zero deletions are allowed.

Therefore, the algorithm returns true exactly when the string can become a palindrome after deleting at most one character.

Complexity

Let n be the length of s.

Metric	Value	Why
Time	`O(n)`	The main scan and one helper scan together inspect a linear number of characters
Space	`O(1)`	Only pointer variables are used

The helper does not create substrings, so the space stays constant.

Implementation

class Solution:
    def validPalindrome(self, s: str) -> bool:
        def is_palindrome_range(left: int, right: int) -> bool:
            while left < right:
                if s[left] != s[right]:
                    return False

                left += 1
                right -= 1

            return True

        left = 0
        right = len(s) - 1

        while left < right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            else:
                return (
                    is_palindrome_range(left + 1, right)
                    or is_palindrome_range(left, right - 1)
                )

        return True

Code Explanation

The helper function checks a substring by index range:

def is_palindrome_range(left: int, right: int) -> bool:

It does not allocate a new string.

It compares both ends:

if s[left] != s[right]:
    return False

If the pair matches, it moves inward:

left += 1
right -= 1

The main loop does the same two-pointer scan on the full string.

When characters match, we continue:

if s[left] == s[right]:
    left += 1
    right -= 1

When characters do not match, we spend our one allowed deletion.

There are only two possible choices:

is_palindrome_range(left + 1, right)

means delete s[left].

is_palindrome_range(left, right - 1)

means delete s[right].

If either choice works, return true.

If the loop finishes, the string was already a palindrome:

return True

Testing

def run_tests():
    s = Solution()

    assert s.validPalindrome("aba") is True
    assert s.validPalindrome("abca") is True
    assert s.validPalindrome("abc") is False

    assert s.validPalindrome("a") is True
    assert s.validPalindrome("aa") is True
    assert s.validPalindrome("ab") is True

    assert s.validPalindrome("deeee") is True
    assert s.validPalindrome("eeeed") is True
    assert s.validPalindrome("abcda") is False

    assert s.validPalindrome("aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxj") is True

    print("all tests passed")

run_tests()

Test meaning:

Test	Expected	Why
`"aba"`	`true`	Already a palindrome
`"abca"`	`true`	Delete one middle character
`"abc"`	`false`	Needs more than one deletion
`"a"`	`true`	Single character is a palindrome
`"aa"`	`true`	Already valid
`"ab"`	`true`	Delete either character
`"deeee"`	`true`	Delete the first character
`"eeeed"`	`true`	Delete the last character
`"abcda"`	`false`	One deletion cannot fix it
Long tricky case	`true`	Checks the helper range logic