# NEETCODE - Two Pointers: Valid Palindrome

Two-Pointer String Validation: From O(n) Extra Space to O(1) In-Place

Technology: **Python, Algorithms**  
Skill: **Two Pointers, String Manipulation**

## Problem Statement

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**.

**Example 1:**

`Input: s = "Was it a car or a cat I saw?"
Output: true
Explanation: After considering only alphanumerical characters we have
 "wasitacaroracatisaw", which is a palindrome.`

**Example 2:**

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

**Constraints:**

- `1 <= s.length <= 1000`
- `s` is made up of only printable ASCII characters

## Solutions Progression

### Approach 1: Clean String + Reverse Comparison

The most intuitive approach: clean the string, reverse it, and compare.

```python
class Solution:
    def isPalindrome(self, s: str) -> bool:
        # Clean: keep only alphanumeric, convert to lowercase
        cleaned = ""
        for char in s:
            if char.isalnum():
                cleaned += char.lower()

# Reverse and compare
        reversed_str = cleaned[::-1]

return cleaned == reversed_str
```

**Time Complexity:** O(n)

- First loop (cleaning): O(n)
- Reversing string: O(n)
- String comparison: O(n)
- Total: O(3n) = O(n)

**Space Complexity:** O(n)

- `cleaned` string: O(n)
- `reversed_str` string: O(n)
- Total: O(2n) = O(n)

**Why this approach works:**

- Simple and straightforward
- Python's string slicing `[::-1]` efficiently reverses
- Easy to understand and debug

**Trade-offs:**

- ✅ Very readable and Pythonic
- ✅ Easy to implement correctly
- ✅ Uses built-in string methods
- ❌ Creates two extra strings (O(n) space)
- ❌ Makes multiple passes through the data
- ❌ Not optimal for space

### Approach 2: Clean String + Index-Based Comparison

Clean the string first, then compare characters from both ends without creating a reversed copy.

```python
class Solution:
    def isPalindrome(self, s: str) -> bool:
        # Clean the string
        cleaned = ""
        for char in s:
            if char.isalnum():
                cleaned += char.lower()

# Compare from both ends
        length = len(cleaned)
        for i in range(length):
            if cleaned[i] != cleaned[length - 1 - i]:
                return False

return True
```

**Time Complexity:** O(n)

- Cleaning loop: O(n)
- Comparison loop: O(n)
- Total: O(2n) = O(n)

**Space Complexity:** O(n)

- `cleaned` string: O(n)

**Why this is better:**

- Eliminates the reversed string copy
- Early termination when mismatch found
- Still O(n) space for cleaned string

### Approach 3: Two Pointers Without Pre-Cleaning (Optimal)

Use two pointers moving from both ends, skipping non-alphanumeric characters on the fly.

```python
class Solution:
    def isPalindrome(self, 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
```

**Time Complexity:** O(n)

- Each character visited at most once
- Total: O(n)

**Space Complexity:** O(1)

- Only using two pointer variables
- No extra string storage

**Why this is optimal:**

1. **No preprocessing:** Validates in a single pass
2. **O(1) space:** Only uses two pointers
3. **Early termination:** Returns False immediately on mismatch
4. **No redundant comparisons:** Each pair compared exactly once

### Approach 4: Two Pointers with Helper Function (Clean Code)

Same logic as Approach 3, but extracted to helper function for readability.

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

while left < right:
            left = self.skip_non_alnum(s, left, 1)
            right = self.skip_non_alnum(s, right, -1)

if left >= right:
                break

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

left += 1
            right -= 1

return True

def skip_non_alnum(self, s: str, index: int, direction: int) -> int:
        """Skip non-alphanumeric characters in given direction"""
        while 0 <= index < len(s) and not s[index].isalnum():
            index += direction
        return index
```

**Time Complexity:** O(n)  
**Space Complexity:** O(1)

**Why this variation matters:**

- Cleaner main logic
- Reusable helper function
- Easier to test and debug
- More maintainable code

### Approach 5: Filter + Two Pointers (Pythonic)

Use Python's list comprehension for filtering, then apply two pointers.

```python
class Solution:
    def isPalindrome(self, s: str) -> bool:
        chars = [c.lower() for c in s if c.isalnum()]
        left, right = 0, len(chars) - 1

while left < right:
            if chars[left] != chars[right]:
                return False
            left += 1
            right -= 1

return True
```

**Time Complexity:** O(n)

- List comprehension: O(n)
- Two-pointer scan: O(n)
- Total: O(2n) = O(n)

**Space Complexity:** O(n)

- `chars` list: O(n) in worst case

**Trade-offs:**

- ✅ Very Pythonic and readable
- ✅ Clean separation of filtering and validation
- ✅ Simple two-pointer logic
- ❌ Uses O(n) space (not optimal)
- ❌ Two passes through data

## Pattern Recognition

**Core Pattern:** Two Pointers Moving Inward

The key insights:

1. **Two pointers eliminate need for string reversal** - Compare from both ends simultaneously
2. **Skip conditions on the fly** - Process characters as you encounter them
3. **O(1) space is achievable** - No need to create cleaned/filtered copies
4. **Early termination** - Stop as soon as mismatch found

This pattern appears whenever you need to:

- Compare elements from both ends of a sequence
- Validate symmetric properties
- Find pairs with specific relationships
- Process arrays/strings without extra space

## Bridge to Real Systems

### Where This Algorithm Lives in Production

**1. DNA Sequence Analysis (Bioinformatics)**

Finding palindromic sequences in DNA (important for restriction enzyme sites):

```python
class DNAAnalyzer:
    def is_palindromic_sequence(self, dna: str) -> bool:
        complement = {'A': 'T', 'T': 'A', 'G': 'C', 'C': 'G'}
        left, right = 0, len(dna) - 1

while left < right:
            if complement.get(dna[left]) != dna[right]:
                return False
            left += 1
            right -= 1

return True
```

### Mini-System Evolution

```python
Level 1: Basic Palindrome Check (What we solved)
→ Validate single string
→ Return true/false
→ Time: O(n), Space: O(1)

Level 2: + Fuzzy Matching
→ Allow k mismatches (almost palindrome)
→ Longest palindromic substring
→ Return edit distance to palindrome

Level 3: + Stream Processing
→ Validate palindromes in text streams
→ Handle multiple languages/encodings
→ Real-time detection

Level 4: + Distributed Text Analysis
→ Process massive document corpus
→ Find all palindromic phrases
→ Rank by length/frequency
→ Parallel processing across nodes
```

## Key Takeaways

01. **Two pointers eliminate need for string reversal** - Compare from both ends simultaneously in O(1) space

02. **Skip conditions can be handled on the fly** - No need to pre-clean the string

03. **Case sensitivity and character filtering are separate concerns** - Handle both independently

04. **Early termination saves time** - Return False as soon as mismatch found

05. **String immutability in Python matters** - Use lists or comprehensions for building strings

06. **The pattern extends to many problems** - Two pointers is fundamental for array/string problems

07. **Space-time trade-off exists** - O(n) space (clean first) vs O(1) space (two pointers)

08. **Boundary conditions are critical** - `left < right` not `left <= right`

09. **Unicode and internationalization matter in production** - Consider normalization

10. **Caching can improve performance** - For repeated validations of same strings.