Palindrome Detection in DSA Python

Mental Model

Check if a sequence reads the same forwards and backwards by comparing characters from both ends moving towards the center.

Analogy: Like checking if a word on a mirror looks the same on both sides, such as 'madam' or 'racecar'.

start -> [m] a d a m ← end
indexes: 0 -> 1 -> 2 -> 3 -> 4

Dry Run Walkthrough

Input: string: 'radar'

Goal: Determine if 'radar' reads the same forwards and backwards

Step 1: Compare first and last characters 'r' and 'r'

r a d a r
↑           ↑
left=0     right=4

Why: Check if characters at both ends match to confirm palindrome property

Step 2: Move inward and compare 'a' and 'a'

r a d a r
  ↑     ↑
left=1 right=3

Why: Continue checking matching pairs moving towards the center

Step 3: Move inward to middle character 'd'

r a d a r
    ↑
left=2 right=2

Why: Middle character doesn't need a pair, so palindrome confirmed

Result:

r a d a r
Palindrome: True

Annotated Code

DSA Python

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

if __name__ == '__main__':
    detector = PalindromeDetector()
    test_string = 'radar'
    result = detector.is_palindrome(test_string)
    print(f"{test_string} -> Palindrome: {result}")

while left < right:

loop to compare characters from both ends moving inward

if s[left] != s[right]:

check if characters at current pointers differ, which breaks palindrome

left += 1 right -= 1

advance pointers inward to next characters for comparison

return True

all pairs matched, confirm string is palindrome

Output

radar -> Palindrome: True

Complexity Analysis

Time: O(n) because we compare pairs of characters from both ends once, where n is string length

Space: O(1) because only two pointers are used regardless of input size

vs Alternative: Compared to reversing the string and comparing, this method uses less space and stops early on mismatch

Edge Cases

empty string

returns True since empty string reads the same forwards and backwards

DSA Python

while left < right:

single character string

returns True because a single character is always a palindrome

DSA Python

while left < right:

string with different characters

returns False as soon as a mismatch is found

DSA Python

if s[left] != s[right]:

When to Use This Pattern

When you need to check if a sequence reads the same forwards and backwards, use two pointers moving inward to compare pairs efficiently.

Common Mistakes

Mistake: Comparing characters only from start to middle without checking the corresponding end character
Fix: Use two pointers, one at start and one at end, and compare both simultaneously

Mistake: Reversing the string and comparing without considering extra space
Fix: Use two-pointer approach to save space and allow early exit on mismatch

Summary

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

Use when you want to verify if a word or sequence is a palindrome efficiently.

The key insight is to use two pointers moving inward to compare pairs, stopping early if mismatch occurs.

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