Valid Palindrome Two Pointer in DSA Python

Mental Model

Use two pointers starting from both ends of the string and move towards the center, comparing characters while skipping non-alphanumeric ones.

Analogy: Imagine two friends starting at opposite ends of a hallway, checking if the tiles they step on match, ignoring broken tiles, and meeting in the middle.

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

Indexes: 0                             29
         ↑                             ↑
        left                         right

Characters compared: s[left] and s[right]

Dry Run Walkthrough

Input: string: "A man, a plan, a canal: Panama"

Goal: Check if the string is a palindrome ignoring spaces, punctuation, and case

Step 1: Initialize left pointer at index 0 and right pointer at index 29

left=0 (A), right=29 (a)

Why: Start comparing characters from both ends

Step 2: Compare characters at left and right after converting to lowercase: 'a' == 'a', move left to 1, right to 28

left=1 ( ), right=28 (m)

Why: Characters match, move inward

Step 3: Skip non-alphanumeric at left (space), move left to 2

left=2 (m), right=28 (m)

Why: Ignore spaces and punctuation

Step 4: Compare 'm' and 'm', move left to 3, right to 27

left=3 (a), right=27 (a)

Why: Characters match, continue inward

Step 5: Compare 'a' and 'a', move left to 4, right to 26

left=4 (n), right=26 (n)

Why: Characters match, continue inward

Step 6: Compare 'n' and 'n', move left to 5, right to 25

left=5 (,), right=25 (a)

Why: Characters match, continue inward

Step 7: Skip non-alphanumeric at left (',' and space), move left to 7

left=7 (a), right=25 (a)

Why: Ignore punctuation and spaces

Step 8: Compare 'a' and 'a', move left to 8, right to 24

left=8 ( ), right=24 (P)

Why: Characters match, continue inward

Step 9: Skip non-alphanumeric at left (space), move left to 9

left=9 (p), right=24 (P)

Why: Ignore spaces

Step 10: Compare 'p' and 'p' (lowercase), characters match, continue similarly until pointers meet

Pointers continue inward successfully

Why: All matching pairs found, confirming palindrome

Result:

String is a palindrome ignoring non-alphanumeric characters and case.
Final pointers crossed or met without mismatch.

Annotated Code

DSA Python

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        while left < right:
            # Skip non-alphanumeric on left
            while left < right and not s[left].isalnum():
                left += 1
            # Skip non-alphanumeric on right
            while left < right and not s[right].isalnum():
                right -= 1
            # Compare characters in lowercase
            if s[left].lower() != s[right].lower():
                return False
            left += 1
            right -= 1
        return True

# Driver code
input_str = "A man, a plan, a canal: Panama"
sol = Solution()
print(sol.isPalindrome(input_str))

while left < right:

continue comparing characters until pointers meet or cross

while left < right and not s[left].isalnum(): left += 1

skip non-alphanumeric characters from the left

while left < right and not s[right].isalnum(): right -= 1

skip non-alphanumeric characters from the right

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

if characters don't match ignoring case, string is not palindrome

left += 1 right -= 1

move pointers inward after successful match

Output

True

Complexity Analysis

Time: O(n) because we scan the string once with two pointers moving inward

Space: O(1) because we use only fixed extra space for pointers

vs Alternative: Compared to creating a filtered reversed string and comparing, this uses less space and is more efficient

Edge Cases

Empty string

Returns True because empty string is trivially palindrome

DSA Python

while left < right:

String with only non-alphanumeric characters

Skips all characters and returns True

DSA Python

while left < right and not s[left].isalnum():

Single character string

Returns True because single character is palindrome

DSA Python

while left < right:

When to Use This Pattern

When you need to check if a string reads the same forward and backward ignoring spaces and punctuation, use the two-pointer palindrome pattern for efficient checking.

Common Mistakes

Mistake: Not skipping non-alphanumeric characters before comparing
Fix: Add loops to skip non-alphanumeric characters on both pointers before comparison

Mistake: Comparing characters without converting to lowercase
Fix: Convert both characters to lowercase before comparing

Mistake: Moving pointers incorrectly causing infinite loop or skipping checks
Fix: Move pointers only after successful character match

Summary

Checks if a string is a palindrome ignoring case and non-alphanumeric characters.

Use when you want to verify palindrome property in strings with spaces and punctuation.

The key insight is to use two pointers moving inward, skipping unwanted characters, and comparing lowercase characters.