# LeetCode 125: Valid Palindrome

## Problem Restatement

We are given a string `s`.

We need to decide whether it is a palindrome after:

1. Converting uppercase letters to lowercase.
2. Removing all non-alphanumeric characters.

Alphanumeric characters are letters and digits. The official problem asks us to return `true` if the cleaned string reads the same forward and backward.

For example:

```python
s = "A man, a plan, a canal: Panama"
```

After cleaning, it becomes:

```python
"amanaplanacanalpanama"
```

This reads the same forward and backward, so the answer is:

```python
True
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `s` |
| Output | `True` if it is a valid palindrome, otherwise `False` |
| Ignore | Non-alphanumeric characters |
| Case | Case-insensitive |
| Empty cleaned string | Palindrome |

The function shape is:

```python
class Solution:
    def isPalindrome(self, s: str) -> bool:
        ...
```

## Examples

For:

```python
s = "A man, a plan, a canal: Panama"
```

The cleaned lowercase string is:

```python
"amanaplanacanalpanama"
```

It is a palindrome, so the answer is:

```python
True
```

For:

```python
s = "race a car"
```

The cleaned lowercase string is:

```python
"raceacar"
```

This does not read the same backward, so the answer is:

```python
False
```

For:

```python
s = " "
```

After removing non-alphanumeric characters, the cleaned string is empty.

An empty string is treated as a palindrome, so the answer is:

```python
True
```

## First Thought: Clean Then Compare

A simple solution is:

1. Build a new string containing only lowercase alphanumeric characters.
2. Compare that string with its reverse.

For example:

```python
cleaned = "amanaplanacanalpanama"
```

Then check:

```python
cleaned == cleaned[::-1]
```

This works, but it uses extra space for the cleaned string.

We can avoid that with two pointers.

## Key Insight

A palindrome compares characters from both ends.

We can keep two pointers:

| Pointer | Starts at | Moves |
|---|---|---|
| `left` | Beginning of string | Rightward |
| `right` | End of string | Leftward |

At each step:

1. Move `left` until it points to an alphanumeric character.
2. Move `right` until it points to an alphanumeric character.
3. Compare lowercase versions of both characters.
4. If they differ, return `False`.
5. Otherwise, move both pointers inward.

If the pointers meet or cross, all valid character pairs matched.

## Algorithm

Initialize:

```python
left = 0
right = len(s) - 1
```

While `left < right`:

1. If `s[left]` is not alphanumeric, increment `left`.
2. Else if `s[right]` is not alphanumeric, decrement `right`.
3. Else compare:

```python
s[left].lower() == s[right].lower()
```

4. If they differ, return `False`.
5. Move both pointers inward.

Return `True`.

## Correctness

The algorithm compares the first relevant character with the last relevant character, then the second relevant character with the second-to-last relevant character, and so on.

Non-alphanumeric characters are skipped by moving the corresponding pointer. Therefore, they never affect the comparison.

When both pointers are on alphanumeric characters, the algorithm compares their lowercase forms. This exactly matches the case-insensitive requirement.

If any pair differs, the cleaned string cannot be a palindrome, so returning `False` is correct.

If the pointers meet or cross, every corresponding pair in the cleaned string has matched. Therefore, the cleaned string reads the same forward and backward, so returning `True` is correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each pointer moves across the string at most once |
| Space | `O(1)` | No cleaned copy is stored |

Here, `n = len(s)`.

## Implementation

```python
class Solution:
    def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s) - 1

        while left < right:
            if not s[left].isalnum():
                left += 1
            elif not s[right].isalnum():
                right -= 1
            else:
                if s[left].lower() != s[right].lower():
                    return False

                left += 1
                right -= 1

        return True
```

## Code Explanation

Start pointers at both ends:

```python
left = 0
right = len(s) - 1
```

Continue while there are pairs to compare:

```python
while left < right:
```

Skip invalid characters on the left:

```python
if not s[left].isalnum():
    left += 1
```

Skip invalid characters on the right:

```python
elif not s[right].isalnum():
    right -= 1
```

When both characters are valid, compare them case-insensitively:

```python
if s[left].lower() != s[right].lower():
    return False
```

Then move inward:

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

If no mismatch is found:

```python
return True
```

## Testing

```python
class Solution:
    def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s) - 1

        while left < right:
            if not s[left].isalnum():
                left += 1
            elif not s[right].isalnum():
                right -= 1
            else:
                if s[left].lower() != s[right].lower():
                    return False

                left += 1
                right -= 1

        return True

def run_tests():
    sol = Solution()

    assert sol.isPalindrome("A man, a plan, a canal: Panama") is True

    assert sol.isPalindrome("race a car") is False

    assert sol.isPalindrome(" ") is True

    assert sol.isPalindrome(".,") is True

    assert sol.isPalindrome("0P") is False

    assert sol.isPalindrome("ab_a") is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"A man, a plan, a canal: Panama"` | Standard palindrome with spaces and punctuation |
| `"race a car"` | Standard false case |
| `" "` | Cleaned string is empty |
| `".,"` | All characters are ignored |
| `"0P"` | Digits are alphanumeric and must be compared |
| `"ab_a"` | Underscore is ignored, giving `"aba"` |