Valid Palindrome: Two pointers Pattern

Learning Outcome

After this lesson, you should be able to compare a string from both ends while skipping non-alphanumeric characters.

Problem Statement

Given a string, return true if it reads the same forward and backward after converting uppercase letters to lowercase and removing non-alphanumeric characters.

Brute Force Approach

Build a new normalized string, reverse it, and compare both strings.

This is simple but uses O(n) extra space for the normalized copy and reversed copy.

Optimized Approach

Use two pointers: one at the start and one at the end. Skip non-alphanumeric characters. Compare lowercase versions of the valid characters. If any pair differs, return false.

Exact Pseudocode

left = 0
right = length(s) - 1
while left < right:
  while left < right and s[left] is not alphanumeric:
    left = left + 1
  while left < right and s[right] is not alphanumeric:
    right = right - 1
  if lowercase(s[left]) != lowercase(s[right]):
    return false
  left = left + 1
  right = right - 1
return true
  

Reference Code

class Solution:
    def isPalindrome(self, s):
        left = 0
        right = len(s) - 1

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

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

            left += 1
            right -= 1

        return True
  

Sample Dry Run

Complexity

Edge Cases

• Only punctuation, such as "!!!", should return true.
• Mixed uppercase and lowercase letters.
• Digits mixed with letters.

Interview Checklist

• Confirm the normalization rule.
• Skip invalid characters before comparing.
• Compare lowercase characters.

FAQs