LeetCode 125: Valid Palindrome

Problem Restatement

We are given a string s.

We need to decide whether it is a palindrome after:

1. Converting uppercase letters to lowercase.
2. Removing all non-alphanumeric characters.

Alphanumeric characters are letters and digits. The official problem asks us to return true if the cleaned string reads the same forward and backward.

For example:

s = "A man, a plan, a canal: Panama"

After cleaning, it becomes:

"amanaplanacanalpanama"

This reads the same forward and backward, so the answer is:

True

Input and Output

Item	Meaning
Input	A string s
Output	True if it is a valid palindrome, otherwise False
Ignore	Non-alphanumeric characters
Case	Case-insensitive
Empty cleaned string	Palindrome

The function shape is:

class Solution:
    def isPalindrome(self, s: str) -> bool:
        ...

Examples

For:

s = "A man, a plan, a canal: Panama"

The cleaned lowercase string is:

"amanaplanacanalpanama"

It is a palindrome, so the answer is:

True

For:

s = "race a car"

The cleaned lowercase string is:

"raceacar"

This does not read the same backward, so the answer is:

False

For:

s = " "

After removing non-alphanumeric characters, the cleaned string is empty.

An empty string is treated as a palindrome, so the answer is:

True

First Thought: Clean Then Compare

A simple solution is:

1. Build a new string containing only lowercase alphanumeric characters.
2. Compare that string with its reverse.

For example:

cleaned = "amanaplanacanalpanama"

Then check:

cleaned == cleaned[::-1]

This works, but it uses extra space for the cleaned string.

We can avoid that with two pointers.

Key Insight

A palindrome compares characters from both ends.

We can keep two pointers:

Pointer	Starts at	Moves
left	Beginning of string	Rightward
right	End of string	Leftward

At each step:

1. Move left until it points to an alphanumeric character.
2. Move right until it points to an alphanumeric character.
3. Compare lowercase versions of both characters.
4. If they differ, return False.
5. Otherwise, move both pointers inward.

If the pointers meet or cross, all valid character pairs matched.

Algorithm

Initialize:

left = 0
right = len(s) - 1

While left < right:

1. If s[left] is not alphanumeric, increment left.
2. Else if s[right] is not alphanumeric, decrement right.
3. Else compare:

s[left].lower() == s[right].lower()

4. If they differ, return False.
5. Move both pointers inward.

Return True.

Correctness

The algorithm compares the first relevant character with the last relevant character, then the second relevant character with the second-to-last relevant character, and so on.

Non-alphanumeric characters are skipped by moving the corresponding pointer. Therefore, they never affect the comparison.

When both pointers are on alphanumeric characters, the algorithm compares their lowercase forms. This exactly matches the case-insensitive requirement.

If any pair differs, the cleaned string cannot be a palindrome, so returning False is correct.

If the pointers meet or cross, every corresponding pair in the cleaned string has matched. Therefore, the cleaned string reads the same forward and backward, so returning True is correct.

Complexity

Metric	Value	Why
Time	O(n)	Each pointer moves across the string at most once
Space	O(1)	No cleaned copy is stored

Here, n = len(s).

Implementation

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

        while left < right:
            if not s[left].isalnum():
                left += 1
            elif not s[right].isalnum():
                right -= 1
            else:
                if s[left].lower() != s[right].lower():
                    return False

                left += 1
                right -= 1

        return True

Code Explanation

Start pointers at both ends:

left = 0
right = len(s) - 1

Continue while there are pairs to compare:

while left < right:

Skip invalid characters on the left:

if not s[left].isalnum():
    left += 1

Skip invalid characters on the right:

elif not s[right].isalnum():
    right -= 1

When both characters are valid, compare them case-insensitively:

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

Then move inward:

left += 1
right -= 1

If no mismatch is found:

return True

Testing

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

        while left < right:
            if not s[left].isalnum():
                left += 1
            elif not s[right].isalnum():
                right -= 1
            else:
                if s[left].lower() != s[right].lower():
                    return False

                left += 1
                right -= 1

        return True

def run_tests():
    sol = Solution()

    assert sol.isPalindrome("A man, a plan, a canal: Panama") is True

    assert sol.isPalindrome("race a car") is False

    assert sol.isPalindrome(" ") is True

    assert sol.isPalindrome(".,") is True

    assert sol.isPalindrome("0P") is False

    assert sol.isPalindrome("ab_a") is True

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
"A man, a plan, a canal: Panama"	Standard palindrome with spaces and punctuation
"race a car"	Standard false case
" "	Cleaned string is empty
".,"	All characters are ignored
"0P"	Digits are alphanumeric and must be compared
"ab_a"	Underscore is ignored, giving "aba"