125. Valid PalindromeEasy

Valid Palindrome

EasyTwo PointersString·MicrosoftAmazonApple

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

"amanaplanacanalpanama" is a palindrome.

Example 2:

Input:s = "race a car"

Output:false

"raceacar" is not a palindrome.

Constraints:

1 ≤ s.length ≤ 2 * 10⁵
s consists only of printable ASCII characters.

Brute Force Approach — Build Filtered String

O(n) Space

🧹

Filter, Then Compare with Reverse

Time O(n)Space O(n)

Filter out all non-alphanumeric characters, lowercase the result, then check if it equals its own reverse. Simple but uses O(n) extra space.

1Build a filtered string keeping only alphanumeric characters, converted to lowercase.
2Return filtered == filtered[::-1].

Why it's not optimal: Allocates an O(n) filtered string and another O(n) for the reversed copy. The two-pointer approach avoids this with O(1) space.

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

Optimal Approach — Two Pointers

O(n) Time

👆

Two Pointers Meeting in the Middle

Time O(n)Space O(1)

We can eliminate the need for creating a new filtered string by using two pointers starting from the ends of the original string. This uses O(1) space memory!

1Initialize pointers l = 0 and r = len(s) - 1.
2While l < r, gracefully skip any non-alphanumeric characters by moving l++ or r--.
3Once both points sit on valid characters, check if s[l].lower() == s[r].lower().
4If they don't match, return False immediately.
5If they do, shift both pointers inward. Repeat till they cross.

String Array: s

READYPress ▶ or step forward to begin.

✓

—

String s

Executing Code

def isPalindrome(s: str) -> bool:

    l, r = 0, len(s) - 1

    while l < r:

        while l < r and not s[l].isalnum():

            l += 1

        while l < r and not s[r].isalnum():

            r -= 1

        if s[l].lower() != s[r].lower():

            return False

        l, r = l + 1, r - 1

    return True

Discussion

…

Loading comments…

LeetMotion