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.

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.

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.

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:

No preprocessing: Validates in a single pass
O(1) space: Only uses two pointers
Early termination: Returns False immediately on mismatch
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.

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.

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:

Two pointers eliminate need for string reversal - Compare from both ends simultaneously
Skip conditions on the fly - Process characters as you encounter them
O(1) space is achievable - No need to create cleaned/filtered copies
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):

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

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

Two pointers eliminate need for string reversal - Compare from both ends simultaneously in O(1) space
Skip conditions can be handled on the fly - No need to pre-clean the string
Case sensitivity and character filtering are separate concerns - Handle both independently
Early termination saves time - Return False as soon as mismatch found
String immutability in Python matters - Use lists or comprehensions for building strings
The pattern extends to many problems - Two pointers is fundamental for array/string problems
Space-time trade-off exists - O(n) space (clean first) vs O(1) space (two pointers)
Boundary conditions are critical - left < right not left <= right
Unicode and internationalization matter in production - Consider normalization
Caching can improve performance - For repeated validations of same strings.