Leetcode - 125. Valid Palindrome

Easy

Dec 22, 2025

#two-pointers

#string

125. Valid Palindrome

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. Alphanumeric characters include letters and numbers.

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
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

1 <= s.length <= 2 * 105
s consists only of printable ASCII characters.

Constraints:

Notes

Intuition

A palindrome reads the same forwards and backwards. By comparing characters from both ends moving toward the center, we can verify this property in a single pass.

Implementation

Use left and right pointers starting at opposite ends. Iterate while l < r, comparing characters at each position. If they don't match, return False immediately. If the loop completes, the string is a valid palindrome.

Edge-cases

The input may contain non-alphanumeric characters and mixed case. Convert the string to lowercase first, then skip over any non-alphanumeric characters during traversal by incrementing/decrementing the pointers without comparing.

Time: O(n) — each character visited at most once
Space: O(1) — only using pointers

Complexity

Solution

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1
        s = s.lower()
        while l < r:
            if not s[l].isalnum():
                l += 1
                continue
            if not s[r].isalnum():
                r -= 1
                continue

            if s[l] != s[r]:
                return False
            
            l += 1
            r -= 1

        return True
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()