Valid Palindrome Two Pointer in DSA Python - Execution Trace

Concept Flow - Valid Palindrome Two Pointer

Start with left=0, right=len(s)-1

↓

Check if s[left

Yes↓

Check if s[right

Yes↓

Compare s[left

Not Equal↓

Return False

↓

Repeat until left >= right

↓

Return True

Two pointers start at the string ends, skip non-alphanumeric chars, compare characters, move inward until pointers cross or mismatch.

Execution Sample

DSA Python

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

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

Execution Table

Step	Operation	left	right	s[left]	s[right]	Action	Result
1	Initialize pointers	0	14	A	a	Compare 'A' and 'a'	Equal (case-insensitive), move inward
2	Move pointers	1	13		r	s[left] is space, skip left	left=2
3	Skip non-alnum left	2	13	m	r	Compare 'm' and 'r'	Not equal, return False
4	Exit	-	-	-	-	-	Palindrome check failed at step 3

💡 Mismatch found at step 3, characters 'm' and 'r' differ ignoring case

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
left	0	1	2	-	-
right	14	13	13	-	-
s[left]	A		m	-	-
s[right]	a	r	r	-	-

Key Moments - 3 Insights

Why do we skip characters that are not alphanumeric?

Because the palindrome check ignores spaces and punctuation. See execution_table step 2 where left pointer skips a space.

Why do we compare characters in lowercase?

To make the check case-insensitive. In step 1, 'A' and 'a' are considered equal after lowering.

What happens when characters don't match?

The function returns False immediately, as shown in step 3 where 'm' and 'r' differ.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'left' after step 2?

A 2

B 1

C 0

D 3

💡 Hint

Check the 'left' column in execution_table row for step 2

At which step does the function decide the string is not a palindrome?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Result' column where it returns False

If the input string had no spaces, how would step 2 change?

A left pointer would not skip and stay same

B right pointer would skip instead

C left pointer would skip more characters

D Function would return True immediately

💡 Hint

Refer to step 2 where left pointer skips space; no spaces means no skip

Concept Snapshot

Two pointers start at string ends
Skip non-alphanumeric chars
Compare lowercase chars
If mismatch, return False
If pointers cross, return True

Full Transcript

This concept uses two pointers starting at the beginning and end of the string. Each pointer moves inward, skipping characters that are not letters or numbers. Characters are compared in lowercase to ignore case differences. If any pair does not match, the function returns False immediately. If the pointers cross without mismatches, the string is a palindrome and returns True.

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