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.

Practice

1. What does the two-pointer technique check when verifying if a string is a palindrome?

easy

A. It counts the number of vowels in the string

B. It compares characters from the start and end moving towards the center

C. It reverses the string and compares with the original

D. It sorts the characters and checks if sorted string equals original

Solution

1. Step 1: Understand two-pointer technique

   Two pointers start at the beginning and end of the string.

2. Step 2: Compare characters moving inward

   Characters at both pointers are compared; pointers move closer if equal.

3. Final Answer:

   It compares characters from the start and end moving towards the center -> Option B

4. Quick Check:

   Two-pointer palindrome check = comparing ends [OK]

Hint: Compare characters from both ends moving inward [OK]

Common Mistakes:

• Thinking it reverses the string
• Checking only vowels or sorting characters
• Using one pointer only

2. Which of the following is the correct syntax to initialize two pointers for a palindrome check in Python?

easy

A. left = 1; right = len(s)

B. left = -1; right = len(s) + 1

C. left = len(s); right = 0

D. left = 0; right = len(s) - 1

Solution

1. Step 1: Identify pointer start positions

   Left pointer starts at 0 (first character), right pointer at last index (length - 1).

2. Step 2: Check syntax correctness

   left = 0; right = len(s) - 1 correctly sets left=0 and right=len(s)-1 for valid indexing.

3. Final Answer:

   left = 0; right = len(s) - 1 -> Option D

4. Quick Check:

   Start pointers at 0 and last index [OK]

Hint: Start left at 0 and right at length minus one [OK]

Common Mistakes:

• Starting right pointer at length (out of range)
• Starting left pointer at 1 (skips first char)
• Using negative or invalid indices

3. What will be the output of the following code?

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

print(is_palindrome('racecar'))
print(is_palindrome('hello'))

medium

A. True\nTrue

B. False\nTrue

C. True\nFalse

D. False\nFalse

Solution

1. Step 1: Check 'racecar' palindrome

   Characters match from both ends, so returns True.

2. Step 2: Check 'hello' palindrome

   Characters differ ('h' != 'o'), returns False.

3. Final Answer:

   True\nFalse -> Option C

4. Quick Check:

   'racecar' palindrome = True, 'hello' not = False [OK]

Hint: Check characters from ends; mismatch means False [OK]

Common Mistakes:

• Assuming 'hello' is palindrome
• Returning True without full check
• Mixing up True/False outputs

4. Find the error in this palindrome check code:

def check_palindrome(s):
    left, right = 0, len(s)
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

medium

A. right should be initialized as len(s) - 1

B. left should start at 1

C. The while condition should be left <= right

D. The function should return False at the end

Solution

1. Step 1: Check pointer initialization

   Right pointer is set to len(s), which is out of string index range.

2. Step 2: Correct pointer initialization

   Right should be len(s) - 1 to point to last character index.

3. Final Answer:

   right should be initialized as len(s) - 1 -> Option A

4. Quick Check:

   Right pointer must be last index, not length [OK]

Hint: Right pointer = length minus one, not length [OK]

Common Mistakes:

• Using len(s) as index causes IndexError
• Changing left pointer start incorrectly
• Incorrect loop condition

5. Given the string s = "A man, a plan, a canal: Panama", which modification is needed in the two-pointer palindrome check to correctly identify it as a palindrome?

hard

A. Ignore non-alphanumeric characters and case during comparison

B. Reverse the string and compare directly

C. Only compare vowels in the string

D. Convert string to uppercase and compare characters directly

Solution

1. Step 1: Understand input complexity

   String contains spaces, commas, and mixed case which affect direct comparison.

2. Step 2: Modify comparison logic

   Skip non-alphanumeric characters and compare lowercase versions to ignore case and symbols.

3. Step 3: Why other options fail

   Reversing or uppercase alone won't ignore spaces/punctuation; vowels only is incorrect.

4. Final Answer:

   Ignore non-alphanumeric characters and case during comparison -> Option A

5. Quick Check:

   Clean string and ignore case for palindrome check [OK]

Hint: Skip symbols and compare lowercase chars [OK]

Common Mistakes:

• Not ignoring punctuation and spaces
• Only changing case without skipping symbols
• Comparing vowels only