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

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:

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:

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:

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:

1. Set left = 0.
2. Set right = len(s) - 1.
3. 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.
4. If the loop finishes, the original string is already a palindrome, so return true.

Walkthrough

Consider:

s = "abca"

Start:

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:

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.

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: