# Valid Palindrome

[link](https://leetcode.com/problems/valid-palindrome/) · Easy · `two pointers`, `string`

> "compare the start with the end" (palindromes, reversing in place, pair sums on a sorted array) → two pointers moving inward, O(1) space. When some elements must be ignored, skip them with inner while loops that also check left < right.

## Problem

> Given a string `s`, return `true` if it is a palindrome, otherwise return `false`.
> A palindrome is a string that reads the same forward and backward. It is also
> case-insensitive and ignores all non-alphanumeric characters.
> (Alphanumeric characters are letters `A-Z`, `a-z` and digits `0-9`.)

**Example 1**
```
Input:  s = "Was it a car or a cat I saw?"
Output: true
```
After keeping only alphanumerics and lowercasing: `"wasitacaroracatisaw"`, a palindrome.

**Example 2**
```
Input:  s = "tab a cat"
Output: false
```
`"tabacat"` is not a palindrome.

**Constraints**
- `1 <= len(s) <= 1000`
- `s` is made up of only printable ASCII characters.

## Thinking

- **Brute force idea:** build a cleaned copy (alphanumerics only, lowercased), reverse it and
  compare → $O(n)$ time, but $O(n)$ extra space for the copy and its reverse.
- **Key insight:** a palindrome means `s[i]` matches `s[n-1-i]`. So compare from **both ends
  inward with two pointers**, skipping characters that don't count. No copy needed → $O(1)$ space.
- **Edge cases to remember:** a string with no alphanumerics at all (`"?!"`, `" "`) is a
  palindrome (the empty string); mixed case (`"Aa"`); digits count (`"0P"` is **not** a palindrome);
  the skip loops must also check `left < right` so they can't run off the end.

## Solution

### Approach A — my solution (two pointers, skip non-alphanumerics) ✅ best practice
**Complexity:** Time $O(n)$ · Space $O(1)$

Already optimal: each pointer only moves inward, so every character is visited at most once,
and nothing is copied. The inner `while` loops guard with `left < right`, so a string full of
punctuation can't push the pointers out of bounds.

```python
def is_palindrome(s: str) -> bool:
    left = 0
    right = len(s) - 1

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

### Approach B — clean, then compare with the reverse (Pythonic)
**Complexity:** Time $O(n)$ · Space $O(n)$ (the cleaned string and its reversed copy)

The brute force from the hints. Shortest to write, and fast in practice because the
work happens in C, but it uses extra memory, which is what the follow-up asks you to avoid.

```python
def is_palindrome_reverse(s: str) -> bool:
    cleaned = "".join(c.lower() for c in s if c.isalnum())
    return cleaned == cleaned[::-1]
```

## Scratch / Experiments

Worst case: a real palindrome (so neither approach can exit early) at the maximum length of 1000
characters, with punctuation and mixed case so the skipping and lowercasing do work.

Approach B is usually faster in wall-clock time despite the extra memory: its loop is a
generator feeding `str.join`, and `[::-1]` and `==` run in C, while Approach A's pointer loop
runs line by line in Python. Same $O(n)$ time; A wins on space, which is the point of the
question.

```python
import random, string

half = "".join(random.choices(string.ascii_letters + string.digits + " ,.!?", k=500))
s = half + half[::-1].swapcase()  # mirror with flipped case: still a palindrome
assert is_palindrome(s) and is_palindrome_reverse(s)
%timeit is_palindrome(s)
%timeit is_palindrome_reverse(s)
```

## Takeaways

- **Pattern:** "compare the start with the end" (palindromes, reversing in place, pair sums on a
  sorted array) → **two pointers moving inward**, $O(1)$ space. When some elements must be
  ignored, skip them with inner `while` loops that **also check `left < right`**.
- **Mistakes I made:** none in the algorithm, it's the optimal solution. Things to keep doing:
  the bounds guard in the skip loops, and comparing `.lower()` on both sides instead of building
  a lowercase copy. (Note: `str.isalnum()` also accepts Unicode letters/digits like `'é'` or `'²'`;
  fine here since the input is ASCII.)
- **Related problems:** Valid Palindrome II (#680, same two pointers, allow one deletion),
  Two Sum II (#167, two pointers on a sorted array), Reverse String (#344, swap from both ends),
  Longest Palindromic Substring (#5, expand from the center instead of shrinking from the ends),
  Palindrome Linked List (#234, no random access, so reverse the second half).

---

From https://taosu.blog/notes/0125-valid-palindrome