Valid Palindrome

Difficulty: Easy Source: NeetCode

Problem

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1: Input: s = "A man, a plan, a canal: Panama" Output: true

Example 2: Input: s = "race a car" Output: false

Example 3: Input: s = " " Output: true

Constraints:

• 1 <= s.length <= 2 * 10^5
• s consists only of printable ASCII characters

Prerequisites

Before attempting this problem, you should be comfortable with:

• Strings — iterating characters, isalnum(), lower()
• Two Pointers — comparing from both ends simultaneously

1. Brute Force

Intuition

Strip out everything that isn’t a letter or digit, lowercase what remains, then compare the cleaned string to its reverse. If they match, it’s a palindrome. This is easy to read and reason about — the only downside is using O(n) extra space for the cleaned string.

Algorithm

1. Build cleaned by iterating s and keeping only characters where c.isalnum() is True, lowercased.
2. Return cleaned == cleaned[::-1].

Solution

def isPalindrome(s):
    cleaned = [c.lower() for c in s if c.isalnum()]
    return cleaned == cleaned[::-1]


print(isPalindrome("A man, a plan, a canal: Panama"))  # True
print(isPalindrome("race a car"))                       # False
print(isPalindrome(" "))                                # True

Complexity

• Time: O(n)
• Space: O(n)

2. Two Pointers

Intuition

Instead of building a cleaned copy, we work directly on the original string. Put one pointer at the far left and one at the far right. Whenever a pointer lands on a non-alphanumeric character, skip it by moving the pointer inward. Once both pointers are on valid characters, compare them (case-insensitively). If they ever differ, it’s not a palindrome. If the pointers cross without a mismatch, it is.

Algorithm

1. Initialize left = 0, right = len(s) - 1.
2. While left < right:
   • Advance left while left < right and s[left] is not alphanumeric.
   • Retreat right while left < right and s[right] is not alphanumeric.
   • If s[left].lower() != s[right].lower(), return False.
   • Move both pointers inward: left += 1, right -= 1.
3. Return True.

Solution

def isPalindrome(s):
    left, right = 0, 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


print(isPalindrome("A man, a plan, a canal: Panama"))  # True
print(isPalindrome("race a car"))                       # False
print(isPalindrome(" "))                                # True

Complexity

• Time: O(n)
• Space: O(1)

Common Pitfalls

Forgetting to lowercase before comparing. 'A' and 'a' are different characters, so always call .lower() (or .upper()) on both sides before the comparison.

Off-by-one in the inner skip loops. The inner while loops must also check left < right, otherwise a pointer can overshoot and the final comparison reads out-of-bounds indices (or compares the same character to itself on an all-non-alphanumeric string).

Treating an all-whitespace string as non-palindrome. After stripping non-alphanumeric characters, an empty sequence is trivially a palindrome — the loop never executes and you return True, which is correct.