Palindrome Detection in DSA Python - Execution Trace

Concept Flow - Palindrome Detection

Start with input string

↓

Set left pointer at start

↓

Set right pointer at end

↓

Compare characters at left and right

↓

Move left++ and right--

↓

Left >= Right?

↓

Repeat compare

↓

Return False

We use two pointers from start and end, compare characters moving inward until mismatch or pointers cross.

Execution Sample

DSA Python

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

Checks if a string reads the same forwards and backwards by comparing characters from both ends.

Execution Table

Step	Operation	Left Pointer	Right Pointer	Characters Compared	Match?	Action	Result So Far
1	Initialize pointers	0	6	-	-	Start comparing	Undecided
2	Compare s[0] and s[6]	0	6	'r' vs 'r'	Yes	Move pointers inward	Undecided
3	Update pointers	1	5	-	-	Continue	Undecided
4	Compare s[1] and s[5]	1	5	'a' vs 'a'	Yes	Move pointers inward	Undecided
5	Update pointers	2	4	-	-	Continue	Undecided
6	Compare s[2] and s[4]	2	4	'c' vs 'c'	Yes	Move pointers inward	Undecided
7	Update pointers	3	3	-	-	Pointers crossed or equal	Undecided
8	Check pointers	3	3	-	-	Left >= Right, return True	Palindrome confirmed

💡 Pointers crossed (left 3 >= right 3), all compared characters matched, string is palindrome

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	Final
left	0	1	2	3	3	3
right	6	5	4	3	3	3
result	Undecided	Undecided	Undecided	Undecided	Palindrome confirmed	Palindrome confirmed

Key Moments - 3 Insights

Why do we stop comparing when left pointer is equal to or greater than right pointer?

Because when left >= right, all character pairs have been checked. See execution_table step 8 where pointers meet, confirming palindrome.

What happens if characters at left and right pointers do not match?

The function immediately returns False, ending the check early. This is shown in the execution_table where 'Match?' would be 'No' and action would be 'Return False'.

Why do we move left pointer forward and right pointer backward after each successful comparison?

To check the next inner pair of characters. This is shown in steps 3, 5, and 7 where pointers update to move inward.

Visual Quiz - 3 Questions

Look at the execution_table, what characters are compared at step 6?

A 'a' vs 'a'

B 'c' vs 'c'

C 'r' vs 'r'

D 'd' vs 'd'

💡 Hint

Check the 'Characters Compared' column at step 6 in execution_table.

At which step do the pointers cross or become equal, ending the loop?

A Step 8

B Step 4

C Step 6

D Step 2

💡 Hint

Look at the 'Action' and 'Left Pointer'/'Right Pointer' columns in execution_table for when left >= right.

If the string was 'racecar', what would be the result after step 8?

A Undecided

B Not a palindrome

C Palindrome confirmed

D Error

💡 Hint

Refer to the 'Result So Far' column at step 8 in execution_table.

Concept Snapshot

Palindrome Detection:
- Use two pointers: left at start, right at end
- Compare characters at left and right
- If mismatch, return False immediately
- Move pointers inward if match
- Stop when left >= right
- Return True if all pairs matched

Full Transcript

Palindrome detection checks if a string reads the same forwards and backwards. We start with two pointers: one at the beginning (left) and one at the end (right) of the string. We compare the characters at these pointers. If they match, we move the left pointer forward and the right pointer backward to check the next pair. If at any point the characters do not match, we return False immediately because the string is not a palindrome. We continue this process until the left pointer is equal to or greater than the right pointer, which means all character pairs have been checked and matched. At this point, we return True, confirming the string is a palindrome.

Practice

1. What does it mean if a string is a palindrome?

easy

A. It contains only letters

B. It reads the same forwards and backwards

C. It has an even number of characters

D. It starts and ends with the same letter

Solution

1. Step 1: Understand palindrome definition

   A palindrome is a word or phrase that reads the same forwards and backwards.

2. Step 2: Compare options with definition

   Only It reads the same forwards and backwards matches this definition exactly.

3. Final Answer:

   It reads the same forwards and backwards -> Option B

4. Quick Check:

   Palindrome = Same forwards and backwards [OK]

Hint: Check if string equals its reverse [OK]

Common Mistakes:

• Thinking palindrome means only letters
• Assuming even length only
• Confusing start/end letters with palindrome

2. Which of the following Python code snippets correctly checks if a string s is a palindrome?

easy

A. s == reversed(s)

B. s == s[1:]

C. s == s.reverse()

D. s == s[::-1]

Solution

1. Step 1: Understand string reversal in Python

   The slice s[::-1] returns the reversed string.

2. Step 2: Check each option

   s == s[::-1] compares s to its reversed slice correctly. s == reversed(s) compares to an iterator, not a string. s == s.reverse() tries to use reverse() which is a list method and returns None. s == s[1:] compares to a substring missing the first character.

3. Final Answer:

   s == s[::-1] -> Option D

4. Quick Check:

   Use slicing to reverse string [OK]

Hint: Use s == s[::-1] to check palindrome [OK]

Common Mistakes:

• Using reversed() without join
• Calling reverse() on string
• Comparing to wrong substring

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

def is_palindrome(s):
    return s == s[::-1]

print(is_palindrome('level'))
print(is_palindrome('world'))

medium

A. True\nFalse

B. False\nTrue

C. True\nTrue

D. False\nFalse

Solution

1. Step 1: Check 'level' palindrome status

   'level' reversed is 'level', so is_palindrome('level') returns True.

2. Step 2: Check 'world' palindrome status

   'world' reversed is 'dlrow', which is different, so is_palindrome('world') returns False.

3. Final Answer:

   True\nFalse -> Option A

4. Quick Check:

   'level' palindrome True, 'world' not [OK]

Hint: Check string equals reversed string for each input [OK]

Common Mistakes:

• Assuming all strings are palindrome
• Mixing output order
• Confusing print output format

4. Find the error in this palindrome check function:

def check_palindrome(s):
    for i in range(len(s)):
        if s[i] != s[len(s)-i]:
            return False
    return True

medium

A. Function returns True too early

B. Loop should run only half the string length

C. Index out of range error in s[len(s)-i]

D. No error, function is correct

Solution

1. Step 1: Analyze index usage in loop

   Index len(s)-i is out of range because string indices go from 0 to len(s)-1.

2. Step 2: Identify correct index for reverse comparison

   It should be len(s)-i-1 to avoid index error.

3. Final Answer:

   Index out of range error in s[len(s)-i] -> Option C

4. Quick Check:

   Check index bounds carefully [OK]

Hint: Remember last index is len(s)-1 [OK]

Common Mistakes:

• Off-by-one error in indexing
• Looping full length instead of half
• Ignoring index errors

5. You want to check if a phrase is a palindrome ignoring spaces and capitalization. Which code snippet correctly implements this?

hard

A. s_clean = ''.join(c.lower() for c in s if c.isalpha())\nreturn s_clean == s_clean[::-1]

B. s_clean = s.replace(' ', '')\nreturn s_clean == s_clean[::-1]

C. s_clean = s.lower()\nreturn s_clean == s_clean[::-1]

D. s_clean = ''.join(c for c in s if c.isdigit())\nreturn s_clean == s_clean[::-1]

Solution

1. Step 1: Understand requirements

   We must ignore spaces and capitalization, and consider only letters.

2. Step 2: Analyze each option

   s_clean = ''.join(c.lower() for c in s if c.isalpha())\nreturn s_clean == s_clean[::-1] removes non-letters and lowercases all characters, then checks palindrome. s_clean = s.replace(' ', '')\nreturn s_clean == s_clean[::-1] only removes spaces but keeps punctuation and case. s_clean = s.lower()\nreturn s_clean == s_clean[::-1] keeps punctuation and spaces. s_clean = ''.join(c for c in s if c.isdigit())\nreturn s_clean == s_clean[::-1] keeps digits only, ignoring letters.

3. Final Answer:

   s_clean = ''.join(c.lower() for c in s if c.isalpha())\nreturn s_clean == s_clean[::-1] -> Option A

4. Quick Check:

   Filter letters and lowercase before palindrome check [OK]

Hint: Filter letters and lowercase before checking [OK]

Common Mistakes:

• Only removing spaces
• Ignoring punctuation
• Not lowercasing letters