Valid Palindrome#

Given a string, decide whether it reads the same forward and backward once you ignore case and consider only letters and digits. Punctuation and spaces do not count. Return true if it is a palindrome and false otherwise.

Example#

Input: s = "A man, a plan, a canal: Panama" Output: True, because the cleaned string “amanaplanacanalpanama” reads the same both ways.

Input: s = "race a car" Output: False.

Brute force#

Build a cleaned, lowercased string of only alphanumeric characters, then compare it with its reverse. This is correct but allocates a full extra copy of the string.

• Time: O(n).
• Space: O(n) for the cleaned copy.

Optimal approach#

Use two pointers, one at each end. Skip any character that is not alphanumeric. Compare the two characters after lowercasing them. If they ever differ, it is not a palindrome. Move the pointers toward each other until they cross. This checks the string in place without building a new one.

Python solution#

 1def is_palindrome(s):
 2    left, right = 0, len(s) - 1
 3    while left < right:
 4        while left < right and not s[left].isalnum():
 5            left += 1
 6        while left < right and not s[right].isalnum():
 7            right -= 1
 8        if s[left].lower() != s[right].lower():
 9            return False
10        left += 1
11        right -= 1
12    return True

Complexity#

• Time: O(n), each character is visited at most once.
• Space: O(1), only two index variables.

This problem is a textbook use of the two-pointer technique. Keep practicing with the 60-day challenge.