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

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:

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

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: