# Valid Palindrome

- **Canonical ID**: `valid-palindrome`
- **Canonical URL**: https://dsacheatsheet.com/problems/valid-palindrome
- **Difficulty**: easy
- **Patterns**: Two Pointers
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/valid-palindrome/

## 1. Core Invariant / The Trick

Converging left/right pointers skipping non-alphanumeric characters, comparing lowercased chars in O(1) extra space without allocating filtered strings.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(1)`
- **Proof**: Left and right pointers advance strictly toward each other across at most N characters.

## 3. Minimal Idiomatic Code

### Python
```python
def isPalindrome(s: str) -> bool:
    l, r = 0, len(s) - 1
    while l < r:
        while l < r and not s[l].isalnum(): l += 1
        while l < r and not s[r].isalnum(): r -= 1
        if s[l].lower() != s[r].lower(): return False
        l, r = l + 1, r - 1
    return True
```

### TypeScript
```typescript
export function isPalindrome(s: string): boolean {
  const isAlnum = (c: string) => /[a-zA-Z0-9]/.test(c);
  let l = 0, r = s.length - 1;
  while (l < r) {
    while (l < r && !isAlnum(s[l])) l++;
    while (l < r && !isAlnum(s[r])) r--;
    if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;
    l++; r--;
  }
  return true;
}
```

### C++
```cpp
bool isPalindrome(string s) {
    int l = 0, r = (int)s.size() - 1;
    while (l < r) {
        while (l < r && !isalnum(s[l])) l++;
        while (l < r && !isalnum(s[r])) r--;
        if (tolower(s[l++]) != tolower(s[r--])) return false;
    }
    return true;
}
```

### Java
```java
boolean isPalindrome(String s) {
    int l = 0, r = s.length() - 1;
    while (l < r) {
        while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;
        while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;
        if (Character.toLowerCase(s.charAt(l++)) != Character.toLowerCase(s.charAt(r--))) return false;
    }
    return true;
}
```

### Go
```go
func isPalindrome(s string) bool {
    l, r := 0, len(s)-1
    for l < r {
        for l < r && !isAlnum(s[l]) { l++ }
        for l < r && !isAlnum(s[r]) { r-- }
        if toLower(s[l]) != toLower(s[r]) { return false }
        l++; r--
    }
    return true
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Allocating a reversed cleaned string wastes O(N) memory.

### Follow-ups
- Valid Palindrome II (allow deleting 1 char): on mismatch, check `isPal(l+1, r) || isPal(l, r-1)`.