# 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:

```python
"aba"
```

is a palindrome.

This string:

```python
"abca"
```

can become a palindrome by deleting `'c'`:

```python
"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:

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

## Examples

Example 1:

```python
s = "aba"
```

This is already a palindrome.

Answer:

```python
True
```

Example 2:

```python
s = "abca"
```

The first and last characters match:

```text
a == a
```

The middle part is:

```text
bc
```

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

We can delete `'c'`, giving:

```text
aba
```

Answer:

```python
True
```

Example 3:

```python
s = "abc"
```

Try deleting one character:

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

Answer:

```python
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:

```text
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:

```python
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:

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

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

## Algorithm

Use a helper function:

```python
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:

```python
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'`:

```text
aca
```

This is a palindrome.

Delete right character `'c'`:

```text
aba
```

This is also a palindrome.

Since at least one choice works, return `true`.

Now consider:

```python
s = "abc"
```

Start:

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

Try deleting `'a'`:

```text
bc
```

Not a palindrome.

Try deleting `'c'`:

```text
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

```python
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:

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

It does not allocate a new string.

It compares both ends:

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

If the pair matches, it moves inward:

```python
left += 1
right -= 1
```

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

When characters match, we continue:

```python
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:

```python
is_palindrome_range(left + 1, right)
```

means delete `s[left]`.

```python
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:

```python
return True
```

## Testing

```python
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 |